#include <iostream>
#include <unordered_map>
class TrieNode {
public:
std::unordered_map<char, TrieNode*> children;
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {}
};
class Trie {
private:
TrieNode* root;
public:
Trie() : root(new TrieNode()) {}
void insert(const std::string& word) {
TrieNode* current = root;
for (char ch : word) {
if (current->children.find(ch) == current->children.end()) {
current->children[ch] = new TrieNode();
}
current = current->children[ch];
}
current->isEndOfWord = true;
}
bool search(const std::string& word) const {
const TrieNode* node = findNode(word);
return (node != nullptr) && node->isEndOfWord;
}
bool startsWith(const std::string& prefix) const {
return findNode(prefix) != nullptr;
}
private:
const TrieNode* findNode(const std::string& prefix) const {
const TrieNode* current = root;
for (char ch : prefix) {
if (current->children.find(ch) == current->children.end()) {
return nullptr;
}
current = current->children.at(ch);
}
return current;
}
};
int main() {
Trie trie;
trie.insert("apple");
trie.insert("app");
trie.insert("apricot");
std::cout << std::boolalpha;
std::cout << "Search 'apple': " << trie.search("apple") << std::endl; // Output: true
std::cout << "Search 'app': " << trie.search("app") << std::endl; // Output: true
std::cout << "Search 'apricot': " << trie.search("apricot") << std::endl; // Output: true
std::cout << "Search 'orange': " << trie.search("orange") << std::endl; // Output: false
std::cout << "StartsWith 'ap': " << trie.startsWith("ap") << std::endl; // Output: true
std::cout << "StartsWith 'ora': " << trie.startsWith("ora") << std::endl; // Output: false
return 0;
}