208 - Implement Trie
Written on October 21, 2015
Tweet
Implement a trie with insert, search, and startsWith methods.
class TrieNode {
boolean storeWord = false;
TrieNode[] children = new TrieNode[26];
}
public class Solution {
TrieNode root = new TrieNode();
public void insert (String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
if (curr.children[c - 'a'] == null) {
curr.children[c - 'a'] = new TrieNode();
}
curr = curr.children[c - 'a'];
}
curr.storeWord = true;
}
public boolean search (String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
if (curr.children[c - 'a'] == null) {
return false;
}
curr = curr.children[c - 'a'];
}
return curr.storeWord;
}
public boolean startsWith(String prefix) {
TrieNode curr = root;
for (char c : prefix.toCharArray()) {
if (curr.children[c - 'a'] == null) {
return false;
}
curr = curr.children[c - 'a'];
}
return true;
}
}
class TrieNode(object):
def __init__(self):
self.is_word = False
self.children = {}
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_word = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
curr = self.root
for char in word:
if char not in curr.children:
return False
curr = curr.children[char]
return curr.is_word
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
curr = self.root
for char in prefix:
if char not in curr.children:
return False
curr = curr.children[char]
return True