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.
class TrieNode {
constructor() {
this.children = new Map();
this.isEnd = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children.has(char)) node.children.set(char, new TrieNode());
node = node.children.get(char);
}
node.isEnd = true;
}
search(word) {
let node = this.root;
for (let char of word) {
if (!node.children.has(char)) return false;
node = node.children.get(char);
}
return node.isEnd;
}
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children.has(char)) return false;
node = node.children.get(char);
}
return true;
}
}
Follow-up:
How would you implement a trie with a limited size?
