47. Implement Trie (Prefix Tree)

MediumTrie Design String Hash Table

A trie (prefix tree) stores a set of strings so that words and prefixes can be looked up in time proportional to their length. It powers features like autocomplete and spell checking.

Implement the Trie class:

Trie() creates an empty trie.
insert(word) adds word to the trie. Inserting the same word twice has no extra effect.
search(word) returns true only if word was inserted as a whole word.
startsWith(prefix) returns true if some inserted word begins with prefix. A word counts as a prefix of itself.

Tests call the methods in sequence.

Example 1

Input: ["Trie","insert","search","search","startsWith","insert","search"]
[[],["card"],["card"],["car"],["car"],["car"],["car"]]
Output: [null,null,true,false,true,null,true]

Explanation: After inserting "card", the string "car" is only a prefix, so search("car") is false while startsWith("car") is true. Once "car" is inserted as a word, search("car") becomes true.

Constraints

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters
At most 3 * 10^4 calls in total

💡 Hint 1

Each node represents a prefix, and each edge adds one letter. The root is the empty prefix.

💡 Hint 2

Give each node up to 26 children (an array or a map) and a flag saying whether a word ends exactly here.

💡 Hint 3

search and startsWith walk the same path; they only differ in whether the final node must carry the end-of-word flag.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Each trie node holds its children (keyed by letter) and an end flag. insert walks from the root letter by letter, creating missing children, and sets end on the last node. Both queries share a helper that follows the path for a string and returns the node it reaches, or null if some letter is missing. startsWith only needs that node to exist; search additionally requires its end flag, which is what separates a stored word from a mere prefix.

Time O(L) per call, where L is the length of the word or prefixSpace O(total letters inserted)

class Trie {
  constructor() {
    this.root = { children: new Map(), end: false };
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), end: false });
      node = node.children.get(ch);
    }
    node.end = true;
  }

  search(word) {
    const node = this.find(word);
    return node !== null && node.end;
  }

  startsWith(prefix) {
    return this.find(prefix) !== null;
  }

  find(s) {
    let node = this.root;
    for (const ch of s) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }
}

class Trie {
    private static class Node {
        final Node[] next = new Node[26];
        boolean end;
    }

    private final Node root = new Node();

    public Trie() {}

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (node.next[c] == null) node.next[c] = new Node();
            node = node.next[c];
        }
        node.end = true;
    }

    public boolean search(String word) {
        Node node = find(word);
        return node != null && node.end;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    private Node find(String s) {
        Node node = root;
        for (int i = 0; i < s.length() && node != null; i++) node = node.next[s.charAt(i) - 'a'];
        return node;
    }
}

class Trie {
  constructor() {

  }

  /** @param {string} word */
  insert(word) {

  }

  /**
   * @param {string} word
   * @return {boolean}
   */
  search(word) {

  }

  /**
   * @param {string} prefix
   * @return {boolean}
   */
  startsWith(prefix) {

  }
}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit