LeetCode Solution 208 - Implement Trie (Prefix Tree)

Problem Statement

A Trie (pronounced as "try") or Prefix Tree is a tree data structure used to store strings efficiently. Implement a Trie class that supports the following operations:

• insert(word): Inserts the string word into the Trie.
• search(word): Returns true if the string word is in the Trie (as a complete word).
• startsWith(prefix): Returns true if any word in the Trie starts with the given prefix.

Example

Input:

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // Returns true
trie.search("app");     // Returns false
trie.startsWith("app"); // Returns true
trie.insert("app");
trie.search("app");     // Returns true

---

Optimal Approach: Trie Data Structure

The most efficient way to solve this problem is by using a Trie (Prefix Tree), where each node represents a character and stores children for subsequent characters.

Algorithm Steps:

1. Insertion:
   • Traverse the Trie based on the characters in word.
   • Create new nodes as needed.
   • Mark the last node as the end of a word.
2. Search:
   • Traverse the Trie based on characters in word.
   • If a character is missing, return false.
   • Return true if the last character marks the end of a word.
3. Prefix Search:
   • Similar to search, but return true even if it’s not the end of a word.

---

LeetCode-Compatible C++ Solution

class Trie {
private:
    struct TrieNode {
        bool isEnd;
        TrieNode* children[26];
        TrieNode() {
            isEnd = false;
            fill(begin(children), end(children), nullptr);
        }
    };
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) return false;
            node = node->children[index];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (!node->children[index]) return false;
            node = node->children[index];
        }
        return true;
    }
};

---

Step-by-Step Explanation

1. Node Structure: Each node stores children (26 letters) and an isEnd flag.
2. Insertion: Traverse existing nodes or create new ones.
3. Search: Check if all characters exist and the last character is a word end.
4. Prefix Search: Check if the characters exist without requiring an exact word match.

---

Dry Run with Sample Input

Given Input:

trie.insert("apple");
trie.search("apple");
trie.search("app");
trie.startsWith("app");
trie.insert("app");
trie.search("app");

Execution:

Operation	Trie Structure	Output
Insert "apple"	root → a → p → p → l → e (end)	-
Search "apple"	Found all chars, isEnd = true	✅ True
Search "app"	Found all chars, isEnd = false	❌ False
StartsWith "app"	Found all chars	✅ True
Insert "app"	Mark p as end of word	-
Search "app"	Found all chars, isEnd = true	✅ True

---

Alternative Approaches

1. Using HashMap (Trie Alternative)

• Time Complexity: O(N) for each operation.
• Space Complexity: O(N × 26) for storing all words.
• Why Not? Still a Trie-based approach, but using unordered_map instead of arrays.

2. Using Set Data Structure

• Idea: Store all words in a unordered_set<string>.
• Time Complexity: O(1) for exact search, O(N) for prefix search.
• Why Not? Takes extra space and inefficient for prefix matching.

3. Brute Force (Linear Search in List of Words)

• Time Complexity: O(N) per query.
• Space Complexity: O(N).
• Why Not? Slow for large datasets.

---

Best Solution: Trie Data Structure

Approach	Time Complexity	Space Complexity	Efficiency
Brute Force	O(N) per search	O(N)	❌ Slow
HashMap-Based Trie	O(N) per op	O(N × 26)	❌ Extra Space
Trie (Optimal)	O(N) per op	O(N × 26)	✅ Best

The Trie is the best approach as it efficiently handles insertions, searches, and prefix queries in O(N) time.

---

Conclusion

The Trie Data Structure is the optimal approach for solving the Implement Trie (Prefix Tree) problem, providing efficient insert, search, and prefix matching operations in O(N) time.

Similar Problems for Practice:

1. Design Add and Search Words Data Structure
2. Replace Words
3. Word Search II

This problem is a great example of how Trie structures enable fast lookup operations.