Implement Trie (Prefix Tree)

A Trie (Prefix Tree) is a tree-like data structure used to efficiently store a dynamic set of strings while allowing efficient prefix search. In this problem, you need to implement a Trie data structure that supports the following operations:

1. insert(word): Inserts a word into the Trie.
2. search(word): Returns true if the word is in the Trie, false otherwise.
3. startsWith(prefix): Returns true if there is any word in the Trie that starts with the given prefix, false otherwise.

Sample Input/Output:

Let’s consider a series of operations on the Trie:

1. Insert “apple” into the Trie.
2. Search for “apple” – Output: true.
3. Search for “app” – Output: false.
4. Check if any word starts with “app” – Output: true.
5. Insert “app” into the Trie.
6. Search for “app” – Output: true.

Time and Space Complexity:

The time complexity for each operation (insert, search, startsWith) is O(L), where L is the length of the input word or prefix.

The space complexity of the Trie is O(M), where M is the total number of characters in all inserted words.

C++ Solution:

#include <iostream>
#include <unordered_map>

using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEnd;

    TrieNode() {
        isEnd = false;
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            node = node->children[ch];
        }
        return node->isEnd;
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            node = node->children[ch];
        }
        return true;
    }

private:
    TrieNode* root;
};

int main() {
    Trie trie;

    trie.insert("apple");
    cout << "Search 'apple': " << (trie.search("apple") ? "true" : "false") << endl; // Output: true
    cout << "Search 'app': " << (trie.search("app") ? "true" : "false") << endl; // Output: false
    cout << "Starts with 'app': " << (trie.startsWith("app") ? "true" : "false") << endl; // Output: true

    trie.insert("app");
    cout << "Search 'app': " << (trie.search("app") ? "true" : "false") << endl; // Output: true

    return 0;
}

In this implementation, we define two classes – TrieNode and Trie. The TrieNode class represents a single node in the Trie, and the Trie class is the Trie data structure itself. The Trie has a root node, and each node can have children nodes for each character in the alphabet.

The insert function inserts a word into the Trie by creating new nodes as needed for each character in the word.

The search function checks if a word exists in the Trie by traversing the Trie character by character.

The startsWith function checks if there is any word in the Trie that starts with the given prefix by traversing the Trie character by character.

The main function demonstrates the usage of the Trie by inserting words and performing search and startsWith operations.

The output for the provided test case will be:

Search 'apple': true
Search 'app': false
Starts with 'app': true
Search 'app': true