208. Implement Trie (Prefix Tree) - Detailed Explanation

Problem Statement

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the exact string word is in the trie (i.e., was previously inserted), or false otherwise.
• boolean startsWith(String prefix) Returns true if there is any previously inserted string that starts with the given prefix, or false otherwise.

Examples

Input
["Trie","insert","search","search","startsWith","insert","search"]
[[],       ["apple"],["apple"],["app"],    ["app"],      ["app"],["app"]]

Output
[null,     null,     true,     false,       true,        null,    true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false (only prefix "app" exists)
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true

Constraints

• 1 ≤ word.length, prefix.length ≤ 2000
• word and prefix consist only of lowercase English letters.
• At most 3·10⁴ calls in total will be made to insert, search, and startsWith.

Approach

Trie Node Structure

Each node holds:

• An array (or map) of up to 26 child pointers, one for each lowercase letter.
• A boolean flag isEnd indicating whether a word ends at this node.

Operations

insert(word)

1. Start at the root node.
2. For each character c in word:
   • Compute its index i = c - 'a'.
   • If node.children[i] is null, create a new TrieNode.
   • Move node = node.children[i].
3. After the last character, mark node.isEnd = true.

search(word)

1. Traverse exactly as in insert, but if at any step node.children[i] is null, return false.
2. After processing all chars, return node.isEnd.

startsWith(prefix)

1. Traverse as in search, but do not check isEnd.
2. If you complete the traversal without hitting null, return true.

Complexity Analysis

• Time: O(m) per operation (m = length of word or prefix).
• Space: In the worst case, O(N·L) for storing all inserted words (N words of average length L), since each character may create a new node.

Python Code

Java Code