LeetCode 208 - Implement Trie (Prefix Tree)

作者 QIFAN 日期 2017-01-29
LeetCode 208 - Implement Trie (Prefix Tree)

原题链接: 208. Implement Trie (Prefix Tree)


题干

实现一个 Trie 树。假设只有小写字母。

API:

void insert(String word);
boolean search(String word);
boolean startsWith(String prefix);

思路

Trie 树就是前缀树,每个节点有 26 个孩子。孩子的 index 就代表了它的字母,每个节点需要有一个 boolean 变量来表示是否有以该节点结尾的单词。

代码:

public class Trie {
Node root;
/** Initialize your data structure here. */
public Trie() {
this.root = new Node();
}
/** Inserts a word into the trie. */
public void insert(String word) {
Node curr = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (curr.next[index] == null) {
curr.next[index] = new Node();
}
curr = curr.next[index];
}
curr.end = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Node curr = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (curr.next[index] == null) {
return false;
}
curr = curr.next[index];
}
return curr.end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Node curr = root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (curr.next[index] == null) {
return false;
}
curr = curr.next[index];
}
return true;
}
static class Node {
boolean end;
Node[] next;
public Node() {
end = false;
next = new Node[26];
}
}
}