Implement a trie with
insert
, search
, and startsWith
methods.
Note:
You may assume that all inputs are consist of lowercase letters
You may assume that all inputs are consist of lowercase letters
a-z
.
Solution 1: Implement problem.
class TrieNode {
// Initialize your data structure here.
boolean val=false;
TrieNode[] next=new TrieNode[26];
public TrieNode() {
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
int i=0;
TrieNode x=root;
while (i<word.length()) {
int index=word.charAt(i)-'a';
if (x.next[index]==null) x.next[index]=new TrieNode();
i++;
x=x.next[index];
}
x.val=true;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode x=root;
int i=0;
while (i<word.length()) {
int index=word.charAt(i)-'a';
if (x.next[index]==null) return false;
i++;
x=x.next[index];
}
return x.val;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode x=root;
int i=0;
while (i<prefix.length()) {
int index=prefix.charAt(i)-'a';
if (x.next[index]==null) return false;
i++;
x=x.next[index];
}
return true;
}
}
没有评论:
发表评论