Implement Trie
Source
Implement a trie with insert, search, and startsWith methods.
Example
insert("lintcode")
search("code") // return false
startsWith("lint") // return true
startsWith("linterror") // return false
insert("linterror")
search("lintcode) // return true
startsWith("linterror") // return true
Note
You may assume that all inputs are consist of lowercase
letters a-z.
Java
class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
this.children = new TrieNode[26];
this.isEndOfWord = false;
}
}
public class Solution {
private TrieNode root;
public Solution() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode runner = root;
for(char c : word.toCharArray()){
if(runner.children[c-'a']==null){
runner.children[c-'a'] = new TrieNode();
}
runner = runner.children[c-'a'];
}
runner.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode runner = root;
for(char c : word.toCharArray()){
if(runner.children[c-'a']==null){
return false;
}
runner=runner.children[c-'a'];
}
return runner.isEndOfWord;
}
public boolean startsWith(String prefix) {
TrieNode runner = root;
for(char c : prefix.toCharArray()){
if(runner.children[c-'a']==null){
return false;
}
runner=runner.children[c-'a'];
}
return true;
}
}