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 {
HashMap<Character, TrieNode> children;
boolean isEnd;
public TrieNode() {
children = new HashMap<>();
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) node.children.put(c, new TrieNode());
node = node.children.get(c);
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) return false;
node = node.children.get(c);
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (!node.children.containsKey(c)) return false;
node = node.children.get(c);
}
return true;
}
}Follow-up:
How would you implement a trie with a limited size?
