Counting Words With a Given Prefix

Easy · Arrays & Hashing · Explanation and code example

Trie

How it works

A Trie (prefix tree) is a tree structure where each node represents a character. By inserting only the first few characters of each word (up to the prefix length), we build a compact structure. Each node keeps a count of how many words pass through it. After inserting all words, we traverse the trie following the prefix characters and return the count at the final node.

Steps

  1. Create a Trie data structure where each node has children and a count.
  2. For each word in the array:
    • If the word is at least as long as the prefix, insert the first prefix.length characters into the trie.
    • Increment the count at each node during insertion.
  3. Traverse the trie following the prefix characters.
  4. If any character is missing, return 0.
  5. Otherwise, return the count at the final node.

Complexity

  • Time complexity: O(m * l + n)
  • Space complexity: O(m * l)

Where m is the number of words, n is the length of the string pref and l is the maximum length of a word.

Things to watch for

Checking Contains Instead of Starts With

The problem asks for words that start with the prefix, not words that contain the prefix anywhere. Using a contains/includes check instead of a starts-with check will incorrectly count words where the prefix appears in the middle.

Not Handling Words Shorter Than the Prefix

When manually comparing characters, forgetting to check if the word is at least as long as the prefix leads to index out of bounds errors or incorrect matches.

Python code example

from typing import List

class PrefixNode:
    def __init__(self):
        self.children = {}   # a -> PrefixNode
        self.count = 0

class PrefixTree:
    def __init__(self):
        self.root = PrefixNode()

    def add(self, w: str, length: int) -> None:
        cur = self.root
        for i in range(length):
            if w[i] not in cur.children:
                cur.children[w[i]] = PrefixNode()
            cur = cur.children[w[i]]
            cur.count += 1

    def count(self, pref: str) -> int:
        cur = self.root
        for c in pref:
            if c not in cur.children:
                return 0
            cur = cur.children[c]
        return cur.count

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        prefix_tree = PrefixTree()

        for w in words:
            if len(w) >= len(pref):
                prefix_tree.add(w, len(pref))

        return prefix_tree.count(pref)

C++ code example

struct PrefixNode {
    PrefixNode* children[26];
    int count;
    PrefixNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
        count = 0;
    }
};

class PrefixTree {
public:
    PrefixNode* root;
    PrefixTree() {
        root = new PrefixNode();
    }

    void add(const string& w, int length) {
        PrefixNode* cur = root;
        for (int i = 0; i < length; i++) {
            int idx = w[i] - 'a';
            if (!cur->children[idx]) {
                cur->children[idx] = new PrefixNode();
            }
            cur = cur->children[idx];
            cur->count++;
        }
    }

    int count(const string& pref) {
        PrefixNode* cur = root;
        for (char c : pref) {
            int idx = c - 'a';
            if (!cur->children[idx]) return 0;
            cur = cur->children[idx];
        }
        return cur->count;
    }
};

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        PrefixTree prefixTree;
        for (string& w : words) {
            if ((int)w.size() >= (int)pref.size()) {
                prefixTree.add(w, pref.size());
            }
        }
        return prefixTree.count(pref);
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations