208. Implement Trie (Prefix Tree
2017-04-13 本文已影响8人
DrunkPian0
实现前缀树。
这题画个图就容易懂。
但是在写````search 和startWith```的时候我发现自己还是不够6。应该先判断false的情形，最后利用isWord判断是否到达一个word。
也就是这么写：
public boolean search(String word) {
TrieNode ws = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(ws.children[c - 'a'] == null) return false;
ws = ws.children[c - 'a'];
}
return ws.isWord;
}
完整代码：
class TrieNode {
public char val;
public boolean isWord;
public TrieNode[] children = new TrieNode[26];
public TrieNode() {
}
TrieNode(char c) {
TrieNode node = new TrieNode();
node.val = c;
}
}
public class Trie {
private TrieNode root;
/**
* Initialize your data structure here.
*/
public Trie() {
root = new TrieNode();
root.val = ' ';
}
/**
* Inserts a word into the trie.
*/
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
if (node.children[word.charAt(i) - 'a'] == null) {
node.children[word.charAt(i) - 'a'] = new TrieNode(word.charAt(i));
}
node = node.children[word.charAt(i) - 'a'];
}
node.isWord = true;
}
/**
* Returns if the word is in the trie.
*/
public boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
if (node.children[word.charAt(i) - 'a'] != null) {
//改变指向的方法 相当于二叉树的node.left ,right，只不过trie可以有26棵subtree
node = node.children[word.charAt(i) - 'a'];
} else {
return false;
}
}
return node.isWord;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
if (node.children[prefix.charAt(i) - 'a'] == null) {
return false;
}
//改变指向的方法 相当于二叉树的node.left ,right，只不过trie可以有26棵subtree
node = node.children[prefix.charAt(i) - 'a'];
}
return true;
}
}
