Implement Trie (Prefix Tree)

LeetCode 208: Implement Trie (Prefix Tree) Solution & Explanation

Problem Overview

TL;DR: The optimal solution builds a tree where each node represents a character, allowing insertion and retrieval operations in $O(L)$ time, where $L$ is the length of the word, independent of the dataset size.

The problem requires implementing a data structure known as a Trie (or Prefix Tree). This structure is designed to store strings efficiently to support three specific operations:

1. Insert: Add a new word to the collection.
2. Search: Check if a specific word is present in the collection.
3. StartsWith: Check if there is any word in the collection that begins with a specific prefix.

This is a fundamental design problem. The LeetCode 208 challenge, "Implement Trie (Prefix Tree)," is a standard interview question used to test a candidate's understanding of tree-based data structures and their ability to manipulate pointers or references to manage hierarchical data.

Brute Force Approach for Implement Trie (Prefix Tree)

A naive approach to solving this problem would be to use a standard list or a generic hash set to store the strings.

1. Storage: Maintain a List<String> or HashSet<String>.
2. Insert: Simply append the word to the list or add it to the set.
3. Search: Iterate through the list to check for equality, or use the set's contains method.
4. StartsWith: Iterate through every string in the collection and check if it starts with the given prefix.

1# Pseudo-code for Naive Approach
2class NaiveTrie:
3    def __init__(self):
4        self.store = set()
5
6    def insert(self, word):
7        self.store.add(word)
8
9    def search(self, word):
10        return word in self.store
11
12    def startsWith(self, prefix):
13        # This is the bottleneck
14        for word in self.store:
15            if word.startswith(prefix):
16                return True
17        return False

Why this fails

While HashSet provides $O(1)$ or $O(L)$ access for exact matches (Search), the startsWith operation becomes significantly inefficient. In a HashSet or List, there is no structural relationship between words that share prefixes (e.g., "apple" and "app"). To find a prefix, you must iterate through the entire dataset in the worst case.

If $N$ is the number of words and $L$ is the average length, the brute force startsWith complexity is $O(N \cdot L)$. Given the constraint of up to $3 \times 10^4$ calls, this approach leads to suboptimal performance compared to the Trie structure.

Algorithm Strategy: Design Patterns

To implement the LeetCode 208 Solution, we define a helper class, typically named TrieNode.

The TrieNode Class:

• Links/Children: An array of size 26 (since constraints specify lowercase English letters). Index 0 represents 'a', index 1 represents 'b', etc. Each index stores a pointer to the next TrieNode.
• IsEnd: A boolean flag indicating whether the current node marks the end of a valid word.

The Trie Class:

• Root: Maintains a single TrieNode as the root of the tree.
• Insert Strategy: Iterate through characters of the word. For each character, compute its index (char - 'a'). If the child pointer at that index is null, create a new node. Move the current pointer to this child. After the loop, set isEnd to true on the final node.
• Search Strategy: Traverse the tree following the characters of the word. If a child pointer is null at any point, the word does not exist (return false). If traversal completes, return the isEnd value of the final node.
• StartsWith Strategy: Identical to search, but upon completing the traversal, return true immediately. We do not need to check isEnd because the existence of the node implies the prefix exists.

Execution Flow

Let's trace the execution of insert("app") followed by search("apple").

Initial State:

• Root node exists. All children pointers are null.

Operation: insert("app")

1. Char 'a': Start at Root. Check index 0. It is null. Create new Node A. Move pointer to Node A.
2. Char 'p': Start at Node A. Check index 15 ('p' - 'a'). It is null. Create new Node P1. Move pointer to Node P1.
3. Char 'p': Start at Node P1. Check index 15. It is null. Create new Node P2. Move pointer to Node P2.
4. End of Word: We finished the string "app". Set Node P2.isEnd = true.

Operation: search("apple")

1. Char 'a': Start at Root. Check index 0. Exists (Node A). Move to Node A.
2. Char 'p': Start at Node A. Check index 15. Exists (Node P1). Move to Node P1.
3. Char 'p': Start at Node P1. Check index 15. Exists (Node P2). Move to Node P2.
4. Char 'l': Start at Node P2. Check index 11. It is null.
5. Result: Since the path broke, return false.

Operation: startsWith("app")

1. Traverse 'a' -> 'p' -> 'p' successfully reaching Node P2.
2. String is consumed. Return true (regardless of isEnd).

Proof of Correctness

The correctness of the Trie relies on the unique path property.

1. Insertion Correctness: Every string maps to a unique path of nodes from the root. By marking the final node, we distinguish between the word "app" (where the second 'p' is marked) and "apple" (where 'e' is marked).
2. Search Correctness: The search function follows the exact same deterministic path logic as insertion. It only returns true if the path exists AND the isEnd flag is set, ensuring we don't return true for "app" if only "apple" was inserted (unless "app" was also explicitly inserted).
3. Prefix Correctness: The startsWith function verifies structural existence. If the nodes corresponding to the prefix exist, then by definition, some word was inserted that created this path.

Pattern Reuse Notes

The logic used in LeetCode 208 is foundational for several other string manipulation problems:

• LeetCode 211: Design Add and Search Words Data Structure
  • Reuse: Extends the Trie search function to handle . wildcards using DFS/recursion on the children array.
• LeetCode 720: Longest Word in Dictionary
  • Reuse: Uses DFS on the Trie to find the deepest path where every node in the path has isEnd == true.
• LeetCode 648: Replace Words
  • Reuse: Uses the Trie to find the shortest prefix (closest to root with isEnd == true) for every word in a sentence.
• LeetCode 425: Word Squares
  • Reuse: Uses a Trie to quickly retrieve all words starting with a specific prefix during a backtracking procedure.

Reference Implementation

C++ Solution for LeetCode 208

1class Trie {
2private:
3    struct TrieNode {
4        TrieNode* children[26];
5        bool isEnd;
6
7        TrieNode() {
8            isEnd = false;
9            for (int i = 0; i < 26; i++) {
10                children[i] = nullptr;
11            }
12        }
13    };
14
15    TrieNode* root;
16
17public:
18    Trie() {
19        root = new TrieNode();
20    }
21
22    void insert(string word) {
23        TrieNode* curr = root;
24        for (char c : word) {
25            int index = c - 'a';
26            if (curr->children[index] == nullptr) {
27                curr->children[index] = new TrieNode();
28            }
29            curr = curr->children[index];
30        }
31        curr->isEnd = true;
32    }
33
34    bool search(string word) {
35        TrieNode* curr = root;
36        for (char c : word) {
37            int index = c - 'a';
38            if (curr->children[index] == nullptr) {
39                return false;
40            }
41            curr = curr->children[index];
42        }
43        return curr->isEnd;
44    }
45
46    bool startsWith(string prefix) {
47        TrieNode* curr = root;
48        for (char c : prefix) {
49            int index = c - 'a';
50            if (curr->children[index] == nullptr) {
51                return false;
52            }
53            curr = curr->children[index];
54        }
55        return true;
56    }
57};

Java Solution for LeetCode 208

1class Trie {
2    
3    private class TrieNode {
4        TrieNode[] children;
5        boolean isEnd;
6
7        public TrieNode() {
8            children = new TrieNode[26];
9            isEnd = false;
10        }
11    }
12
13    private TrieNode root;
14
15    public Trie() {
16        root = new TrieNode();
17    }
18
19    public void insert(String word) {
20        TrieNode curr = root;
21        for (char c : word.toCharArray()) {
22            int index = c - 'a';
23            if (curr.children[index] == null) {
24                curr.children[index] = new TrieNode();
25            }
26            curr = curr.children[index];
27        }
28        curr.isEnd = true;
29    }
30
31    public boolean search(String word) {
32        TrieNode curr = root;
33        for (char c : word.toCharArray()) {
34            int index = c - 'a';
35            if (curr.children[index] == null) {
36                return false;
37            }
38            curr = curr.children[index];
39        }
40        return curr.isEnd;
41    }
42
43    public boolean startsWith(String prefix) {
44        TrieNode curr = root;
45        for (char c : prefix.toCharArray()) {
46            int index = c - 'a';
47            if (curr.children[index] == null) {
48                return false;
49            }
50            curr = curr.children[index];
51        }
52        return true;
53    }
54}

Python Solution for LeetCode 208

1class TrieNode:
2    def __init__(self):
3        # Using a list of size 26 for strict pattern adherence
4        # Alternatively, a dictionary can be used: self.children = {}
5        self.children = [None] * 26
6        self.is_end = False
7
8class Trie:
9
10    def __init__(self):
11        self.root = TrieNode()
12
13    def insert(self, word: str) -> None:
14        curr = self.root
15        for char in word:
16            index = ord(char) - ord('a')
17            if not curr.children[index]:
18                curr.children[index] = TrieNode()
19            curr = curr.children[index]
20        curr.is_end = True
21
22    def search(self, word: str) -> bool:
23        curr = self.root
24        for char in word:
25            index = ord(char) - ord('a')
26            if not curr.children[index]:
27                return False
28            curr = curr.children[index]
29        return curr.is_end
30
31    def startsWith(self, prefix: str) -> bool:
32        curr = self.root
33        for char in prefix:
34            index = ord(char) - ord('a')
35            if not curr.children[index]:
36                return False
37            curr = curr.children[index]
38        return True