Implement Trie
Implement a trie with insert, search, and startsWith methods.
Constraints:
- You may assume that all inputs are consist of lowercase letters a-z.
- All inputs are guaranteed to be non-null.
Examples:
Input: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); trie.search("app"); trie.startsWith("app");
Output: true, false, true
Explanation: Inserts 'apple' into the trie, then searches for 'apple' and 'app', and checks if there is any word in the trie that starts with 'app'.
Solutions
Hash Map
Time: O(m)Space: O(n*m)
The solution uses a TrieNode class to represent each node in the trie, with a HashMap to store the children of each node and a boolean to mark the end of a word. The Trie class has methods to insert a word, search for a word, and check if there is any word that starts with a given prefix.
struct TrieNode {
unordered_map<char, TrieNode*> children;
bool isEnd;
TrieNode() : isEnd(false) {
}
}
;
class Trie {
TrieNode* root;
public: Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) node->children[c] = new TrieNode();
node = node->children[c];
}
node->isEnd = true;
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) return false;
node = node->children[c];
}
return node->isEnd;
}
bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (node->children.find(c) == node->children.end()) return false;
node = node->children[c];
}
return true;
}
}Follow-up:
How would you implement a trie with a limited size?
