A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

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 string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Examples

Example 1:

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");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return 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 will be made to insert, search, and startsWith.

Thinking Process

  1. Self-Referential Design: Each Trie object is itself a node, making the structure simpler
  • Strings often need frequency maps or two-pointer scans.
  • Watch index bounds and empty-string edge cases.
  • Stack helps with nested or repeated patterns.
Design pattern API hash + list compose data structures for operations

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Solution

class Trie {
public:
    Trie() : children(26), isWord(false) {
        
    }
    
    void insert(string word) {
        Trie* node = this;
        for(char ch: word) {
            ch -= 'a';
            if(!node->children[ch]) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isWord = true;
    }
    
    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isWord;
    }
    
    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }

private:
    vector<Trie*> children;
    bool isWord;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for(char ch: prefix) {
            ch -= 'a';
            if(!node->children[ch]) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

Solution Explanation

Approach: Two pointers on string (this problem)

Key idea: 1. Self-Referential Design: Each Trie object is itself a node, making the structure simpler

How the code works:

  1. Self-Referential Design: Each Trie object is itself a node, making the structure simpler
    • Strings often need frequency maps or two-pointer scans.
    • Watch index bounds and empty-string edge cases.
    • Stack helps with nested or repeated patterns.

      Common Mistakes

  2. Empty string: Should be handled (mark root as end if needed)
  3. Single character: Works normally
  4. Duplicate insert: Same word inserted twice (safe, just re-marks end)
  5. Prefix of existing word: insert("apple"), then insert("app") works
  6. Word extends prefix: insert("app"), then insert("apple") works
  7. Non-existent search: Returns false correctly

  8. Non-existent prefix: startsWith returns false correctly

  9. Forgetting isWord check: search returns true for prefixes if not checking isWord
  10. Not checking isWord in search: search("app") returns true when only “apple” exists
  11. Character indexing error: Forgetting ch -= 'a' before accessing children[ch]
  12. Index out of bounds: Not validating character is lowercase (0-25 range)
  13. Null pointer access: Not checking if(!node->children[ch]) before accessing
  14. Incorrect traversal: Not updating node = node->children[ch] in loop
  15. Case sensitivity: Assuming only lowercase (problem constraint)
  16. Using this incorrectly: Forgetting that root is this itself, not a separate pointer

When to Use Trie

  1. Autocomplete: Fast prefix matching
  2. Spell Checker: Dictionary lookup
  3. IP Routing: Longest prefix matching
  4. Search Engines: Prefix-based search
  5. Phone Directory: Name/contact lookup
  6. Word Games: Valid word checking

This problem is a fundamental data structure implementation that demonstrates the Trie (Prefix Tree) structure. It’s essential for understanding prefix-based string operations and is widely used in autocomplete systems and search engines.

Key Takeaways

  1. Self-Referential Design: Each Trie object is itself a node, making the structure simpler
  2. Trie Structure: Tree where each path represents a prefix/word
  3. End Marker (isWord): Critical to distinguish between prefix and complete word
  4. Shared Prefixes: Multiple words sharing prefixes share nodes (space efficient)
  5. Array vs Map: vector<Trie*> (26 elements) is faster and uses less memory than unordered_map
  6. Character Indexing: ch -= 'a' converts character to 0-25 index efficiently
  7. Helper Method: searchPrefix reduces code duplication between search and startsWith
  8. Root as this: The Trie object itself serves as the root, eliminating need for separate root pointer

References

Template Reference