Implement Trie (Prefix Tree)

Problem Statement

A trie, also known as a prefix tree, is a specialized tree-like data structure that facilitates the storage and retrieval of strings in a way that keys can be searched for by their prefixes. This characteristic makes tries an ideal solution for functionalities such as autocomplete systems and spellcheckers.

Implement a Trie class with the following functionalities:

• Trie(): Initializes the trie.
• void insert(String word): Inserts the string word into the trie.
• boolean search(String word): Returns true if the word exists in the trie, otherwise returns false.
• boolean startsWith(String prefix): Returns true if any word in the trie starts with the given prefix, otherwise returns false.

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");       // returns true
trie.search("app");         // returns false
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^4 calls in total will be made to insert, search, and startsWith.

Approach and Intuition

Tries offer efficient word and prefix lookups by decomposing strings into character-level nodes:

1. Initialization:

   • The root node is created. Each node maintains a character-to-child mapping and an end-of-word flag.

2. Insertion:

   • For each character in word, traverse or create a child node.
   • After the last character, mark the final node as an end node.

3. Search:

   • Traverse through each character of word.
   • If the full path exists and ends at a word marker, return true; otherwise, return false.

4. Prefix Check:

   • Traverse through the prefix characters.
   • If the path exists regardless of the word-end marker, return true; otherwise, return false.

This character-by-character approach ensures O(L) time complexity for each operation, where L is the length of the input string. It’s ideal for high-frequency word lookups and incremental prefix matching.

Solutions

class Trie {
        
    bool hasPrefix(const string& prefix) {
        TrieNode* currentNode = searchPrefix(prefix);
        return currentNode != nullptr;
    }
}