208.实现Trie (前缀树)

Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。

代码模板如下:

class Trie {
/*
总体思路:
1.创建节点类:TireNode 包含2个成员:
1.boolean end->标记该节点是否为单词末尾
2.TireNode[26] children 孩子触手指向接下来的字母节点
2.通过这个TireNode类进行保存、查找与查询前缀的操作
*/
class TireNode {
boolean end; // 标记该节点是否为单词末尾
TireNode[] children; // 孩子触手指向接下来的字母节点

public TireNode() {
end = false; // 默认不是结尾
children = new TireNode[26]; // 保存字母26只触手即可
}
}

TireNode root; // Tire根节点

public Trie() {
root = new TireNode();
}

// 向前缀树中插入字符串 word
public void insert(String word) {
TireNode p = root; // p指针从Tire根节点开始
for (int i = 0; i < word.length(); i++) {
int u = word.charAt(i) - 'a'; // word[i]对应触手索引
if (p.children[u] == null) p.children[u] = new TireNode(); // 没有对应字母节点就创建
p = p.children[u]; // 往下走
}
p.end = true; // 标记p这里是结尾
}

// 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false
public boolean search(String word) {
TireNode p = root;
for (int i = 0; i < word.length(); i++) {
int u = word.charAt(i) - 'a';
if (p.children[u] == null) return false; // 没有该单词
p = p.children[u];
}
return p.end; // 如果当初p标记了结尾说明就是存在该单词
}

// 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false
public boolean startsWith(String prefix) {
TireNode p = root;
for (int i = 0; i < prefix.length(); i++) {
int u = prefix.charAt(i) - 'a';
if (p.children[u] == null) return false;
p = p.children[u];
}
return true; // 能走完就表明存在该前缀,不一定要为end==true
}
}