A Trie (pronounced "try") is a specialized tree structure designed for efficient string storage and retrieval. This data structure excels at operations like autoocmplete suggestions and spell checking, where prefix-based lookups are frequent.

This implementation provides a Trie class with three core operations:

• Trie() - Creates an empty prefix tree
• insert(word) - Adds a string to the structure
• search(word) - Checks if an exact string exists
• startsWith(prefix) - Checks if any stored string begins with the given prefix

Example:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Constraints:

• 1 <= word.length, prefix.length <= 2000
• Strings consist only of loweracse English letters
• Total operations across all methods do not exceed 30,000

Implementation Details

Each node in the Trie contains a fixed-size array of 26 child pointers (one for each lowercase letter) and a boolean flag indicating whether the node marks the end of a valid word.

Insertion Algorithm:

Starting from the root, traverse character by character. If a required child node doesn't exist, create it. Continue until the final character is processed, then mark that node as a word terminal.

Search Algorithm:

Traverse the path corresponding to each character in the target string. If any character cannot be found in the tree, return false. If traversal completes successful, return true only if the final node is marked as a word terminal.

Prefix Matching:

Similar to search, but no terminal flag check is needed. If the entire prefix path exists in the tree, return true.

Code Implementation:

class PrefixTree {
private:
    static const int ALPHABET_SIZE = 26;
    std::vector<PrefixTree*> branches;
    bool endOfWord;

    PrefixTree* locateNode(const std::string& key) {
        PrefixTree* current = this;
        for (char letter : key) {
            int index = letter - 'a';
            if (current->branches[index] == nullptr) {
                return nullptr;
            }
            current = current->branches[index];
        }
        return current;
    }

public:
    PrefixTree() : branches(ALPHABET_SIZE, nullptr), endOfWord(false) {}

    void insert(const std::string& word) {
        PrefixTree* current = this;
        for (char letter : word) {
            int index = letter - 'a';
            if (current->branches[index] == nullptr) {
                current->branches[index] = new PrefixTree();
            }
            current = current->branches[index];
        }
        current->endOfWord = true;
    }

    bool contains(const std::string& word) {
        PrefixTree* node = locateNode(word);
        return node != nullptr && node->endOfWord;
    }

    bool hasPrefix(const std::string& prefix) {
        return locateNode(prefix) != nullptr;
    }
};

Complexity Analysis:

Time Complexity:

• Construction: O(1)
• Insertion: O(m) where m represents the string length
• Search operations: O(m) where m represents the target string or prefix length

Space Complexity:

• O(S × A) where S is the total number of characters across all inserted strings, and A represents the alphabet size (26 for lowercase letters)