610,实现 Trie (前缀树)
问题描述
来源:LeetCode第208题
难度:中等
Trie(发音类似"try")或者说前缀树是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串word 。
boolean search(String word) 如果字符串word在前缀树中,返回true(即,在检索之前已经插入);否则,返回false。
boolean startsWith(String prefix) 如果之前已经插入的字符串word的前缀之一为prefix,返回true;否则,返回false 。
示例:
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示:
1<=word.length, prefix.length<=2000
word和prefix仅由小写英文字母组成
insert、search和startsWith调用次数总计不超过3*10^4次
问题分析
Trie树也叫字典树,就像查字典一样,比如在字典中我们要找wo,第一步需要找到w,然后第2步再找o。其实我们可以把它看做是一棵n叉树,就是每个节点下面最多有n个子节点。题中说了word和prefix仅由小写英文字母组成,因为小写英文字母有26个,所以我们可以把它看做是一棵26叉树。如下图所示
他有一个根节点,根节点是不存储任何值的,然后根节点下面最多有26个子节点,每个子节点最多又有26个子节点……,比如字符串
“ac”,“bcd”,“ace”,“ef”
在字典树中是这样存在的
但是这里会有一个问题,我们没有储藏字符串“bc”,但上面字典树中包含字符串“bc”,其中还包括字符串“a”,“b”,“e”。实际上他们都不是一个完整的字符串,而是我们储藏字符串的前缀。那么怎么确定是否是一个完整的字符串中,我们需要对字符串的最后一个字符进行标记,如下图所示
如上图所示,因为字符串“bc”的最后一个字符“c”没有被标记,所以字符串“bc”不是一个完整的字符串。至于怎么标记大家可以自己定,这里我们通过一个boolean类标来标记,节点类如下
//创建节点类
class TrieNode {
/**
* 标记是否为完整字符串,如果是字符串的
* 最后一个字符,则为true,否则为false。
*/
boolean isWord;
//26个子节点
TrieNode[] children;
public TrieNode() {
isWord = false;
children = new TrieNode[26];
}
}
注意这里的节点类并没有存储单个字符,我们根据他是否为空来判断相对应的字符是否存在。比如我们查找字符a,因为a是26个节点中的第一个,我们只需要判断第一个子节点是否为空即可。如果为空表示a不存在,否则表示a存在,我们来看下完整代码
public class Trie {
//根节点,根节点是不存储任何字母的,从根节点的
//子节点开始存储
private TrieNode root;
public Trie() {
root = new TrieNode();
}
//插入字符串
public void insert(String word) {
TrieNode parentNode = root;
for (int i = 0; i < word.length(); i++) {
//计算是父节点的哪个子节点
int index = word.charAt(i) - 'a';
//判断字符有没有创建,如果没有创建就创建
if (parentNode.children[index] == null) {
parentNode.children[index] = new TrieNode();
}
//更新父节点
parentNode = parentNode.children[index];
}
//最后一个字符才能构成一个完整的单词
parentNode.isWord = true;
}
//查找,判断是否是个完整的字符串
public boolean search(String word) {
TrieNode current = find(word);
return current != null && current.isWord;
}
//是否以prefix为前缀
public boolean startsWith(String prefix) {
return find(prefix) != null;
}
//查找字典树中是否有str字符串
private TrieNode find(String str) {
TrieNode parentNode = root;
int length = str.length();
for (int i = 0; i < length; i++) {
int index = str.charAt(i) - 'a';
//只要有一个字符节点不存在就返回null
if ((parentNode = parentNode.children[index]) == null)
return null;
}
return parentNode;
}
}
截止到目前我已经写了600多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有1000多页,大家可以在下面公众号“数据结构和算法”中回复关键字“pdf”即可获取下载链接。