Tries: share the start of every word

A trie stores words in a tree where each edge is one letter. So the path from the root down to a node spells a prefix, the start of a word. Words that start the same way share the same path. This means you answer any question about a prefix by walking that prefix once, letter by letter. It doesn't matter how many words you stored.

Think of it like this: a phone's contact search. You type “m” and the list jumps to the M section. You type “ma” and it narrows to Mark, Maria and Matt. You never read through the whole address book. Each letter you type takes you one step further down. Everyone who shares those letters is already grouped together underneath.

How to spot it

Words and constraints in a problem that point to this pattern:

• “Starts with”, “prefix”, “begins with”: many questions about the start of words
• Many words stored once, then many lookups: “add a word”, then “search” or “suggest”
• “As the user types each letter”: autocomplete and search suggestions
• A wildcard such as . that matches any one letter, where a plain Set can't look up the pattern
• A dictionary of words to match against a long text or a grid of letters

Watch it work

The template

class TrieNode {
  children = new Map<string, TrieNode>(); // letter → the child node for that letter
  isEnd = false;                          // true when a stored word ends exactly here
}

class Trie {
  private root = new TrieNode();          // the empty prefix: every walk starts here

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {              // one step down per letter
      let next = node.children.get(ch);
      if (next === undefined) {           // no path for this letter yet
        next = new TrieNode();            // so build it
        node.children.set(ch, next);
      }
      node = next;                        // step down
    }
    node.isEnd = true;                    // mark where the word finishes
  }

  search(word: string): boolean {
    const node = this.walk(word);
    return node !== null && node.isEnd;   // the path exists AND a word ends here
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null;    // the path exists: some word continues from here
  }

  // Follow the letters of text from the root. Return the node reached, or null if a letter is missing.
  private walk(text: string): TrieNode | null {
    let node = this.root;
    for (const ch of text) {
      const next = node.children.get(ch);
      if (next === undefined) return null; // the path breaks: nothing stored starts like this
      node = next;
    }
    return node;
  }
}

// const t = new Trie();
// t.insert("car"); t.insert("cat"); t.insert("do");
// t.search("ca")      → false (a path, but no word ends there)
// t.startsWith("ca")  → true
// t.search("cat")     → true

Worked example

1. The first idea: for each query, loop over every word and count the ones where word.startsWith(query). It's correct, and with 4 words it's instant. With 20,000 words and 20,000 queries, it's 400 million startsWith calls. That takes seconds.

   function countPrefixesSlow(words: string[], queries: string[]): number[] {
     return queries.map((q) => words.filter((w) => w.startsWith(q)).length);
   }
   

2. Notice the waste. The queries "ca" and "car" both re-read "car", "cat" and "cart" from the first letter. Both also check "dog", even though its first letter already rules it out. The words that share a start get compared again and again.

3. In a trie, every word that starts with "ca" passes through the "ca" node on its way down. So let each node keep a counter of how many words passed through it during insert. Then the answer for a query is the counter on the node the query leads to. That is one walk per query, and no loop over the words.

4. Add count to the node. Add 1 to it on every node the insert steps into. Then answer each query with a walk. A query whose path breaks has 0 words.

   class CountNode {
     children = new Map<string, CountNode>();
     count = 0;                               // how many inserted words pass through this node
   }
   
   function countPrefixes(words: string[], queries: string[]): number[] {
     const root = new CountNode();
     for (const word of words) {
       let node = root;
       for (const ch of word) {
         let next = node.children.get(ch);
         if (next === undefined) {
           next = new CountNode();
           node.children.set(ch, next);
         }
         next.count++;                         // this word passes through next
         node = next;
       }
     }
     return queries.map((q) => {
       let node: CountNode | undefined = root;
       for (const ch of q) {
         node = node.children.get(ch);
         if (node === undefined) return 0;     // the path breaks: no word starts like this
       }
       return node.count;
     });
   }
   
   // countPrefixes(["car", "cat", "cart", "dog"], ["ca", "car", "d", "x"]) → [3, 2, 1, 0]
   

5. Check it by hand. Inserting the four words leaves c with count 3, "ca" with 3, "car" with 2 (from "car" and "cart") and d with 1. The query "x" breaks at the first letter and returns 0. Note that count sits on the child we step into, never on the root. The root would count every word, which is the answer for the empty query "".

6. Edge cases: a word inserted twice counts twice, which is what the question asks for. If it should count once, keep a Set of inserted words and skip a word that's already in it. A query longer than every word breaks partway down and returns 0.

Common mistakes

• Forgetting the end-of-word flag. Then search("ca") returns true after inserting only "car", because the path exists even though no word ends there.
• Setting isEnd on every node you pass, or inside the loop instead of after it. Then every prefix of every word looks like a stored word.
• Creating children in search or startsWith by reusing the insert loop. Every failed lookup quietly adds nodes. Later startsWith calls then return true for words never inserted.
• Forgetting to step down (node = next) after creating a child. Every letter gets attached to the root, so "car" is stored as three one-letter branches. Lookups of longer words then fail.
• Checking isEnd in startsWith too. It then answers false for "ca", even though "car" and "cat" start with it. Only search needs the flag.

Cost

In interviews