208. Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
Solution: HashMap
Python
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = dict()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
node = self.root
for char in word:
if char not in node:
node[char] = dict()
node = node[char]
node['#'] = word
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return '#' in node
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
Solution: Array
Java
public class Trie {
class TrieNode {
boolean terminate;
TrieNode[] children = new TrieNode[26];
}
TrieNode root = new TrieNode();
/** Initialize your data structure here. */
public Trie() {
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
if (cur.children[c - 'a'] == null) {
cur.children[c - 'a'] = new TrieNode();
}
cur = cur.children[c - 'a'];
}
cur.terminate = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
if (cur.children[c - 'a'] == null) {
return false;
}
cur = cur.children[c - 'a'];
}
return cur.terminate;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode cur = root;
for (char c : prefix.toCharArray()) {
if (cur.children[c - 'a'] == null) {
return false;
}
cur = cur.children[c - 'a'];
}
return true;
}
}