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:
def __init__(self):
self.children = {}; self.isEnd = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root for char in word:
if char not in node.children:
node.children[char] = TrieNode() node = node.children[char] node.isEnd = True
def search(self, word):
node = self.root for char in word:
if char not in node.children:
return False node = node.children[char] return node.isEnd
def startsWith(self, prefix):
node = self.root for char in prefix:
if char not in node.children:
return False node = node.children[char] return TrueFollow-up:
How would you implement a trie with a limited size?
