【强化练习】Trie 树算法习题
原创约 908 字
本文讲解的例题
有了 TrieMap 和 TrieSet，力扣上所有前缀树相关的题目都可以直接套用了，下面我举几个题目实践一下。
可以尝试优化
首先，前文 TrieMap/TrieSet 代码实现 给出的 TrieMap/TrieSet 执行效率在具体的题目里面肯定是有优化空间的。
比如力扣前缀树相关题目的输入都被限制在小写英文字母 a-z，所以 TrieNode 其实不用维护一个大小为 256 的 children 数组，大小设置为 26 就够了，可以减小时间和空间上的复杂度。
另外，之前给出的 Java/cpp 代码带有泛型，在做算法题的时候其实不需要，去掉泛型也可以获得一定的效率提升。
208. 实现 Trie (前缀树)
先看下力扣第 208 题「实现前缀树」：
208. 实现 Trie (前缀树) | 力扣 | LeetCode |
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 <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过3 * 104次
题目让我们实现的几个函数其实就是 TrieSet 的部分 API，所以直接封装一个 TrieSet 就能解决这道题了：
class Trie {
// 直接封装 TrieSet
TrieSet set = new TrieSet();
// 插入一个元素
public void insert(String word) {
set.add(word);
}
// 判断元素是否在集合中
public boolean search(String word) {
return set.contains(word);
}
// 判断集合中是否有前缀为 prefix 的元素
public boolean startsWith(String prefix) {
return set.hasKeyWithPrefix(prefix);
}
}
// 见上文
class TrieSet {}648. 单词替换
接下来看下力扣第 648 题「单词替换」：
648. 单词替换 | 力扣 | LeetCode |
在英语中，我们有一个叫做 词根(root) 的概念，可以词根 后面 添加其他一些词组成另一个较长的单词——我们称这个词为 衍生词 (derivative)。例如，词根 help，跟随着 继承词 "ful"，可以形成新的单词 "helpful"。
现在，给定一个由许多 词根 组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有 衍生词 用 词根 替换掉。如果 衍生词 有许多可以形成它的 词根，则用 最短 的 词根 替换它。
你需要输出替换之后的句子。
示例 1：
输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" 输出："the cat was rat by the bat"
示例 2：
输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs" 输出："a a b c"
提示：
1 <= dictionary.length <= 10001 <= dictionary[i].length <= 100dictionary[i]仅由小写字母组成。1 <= sentence.length <= 106sentence仅由小写字母和空格组成。sentence中单词的总量在范围[1, 1000]内。sentence中每个单词的长度在范围[1, 1000]内。sentence中单词之间由一个空格隔开。sentence没有前导或尾随空格。
现在你学过 Trie 树结构，应该可以看出来这题就在考察最短前缀问题。
所以可以把输入的词根列表 dict 存入 TrieSet，然后直接复用我们实现的 shortestPrefixOf 函数就行了：
String replaceWords(List<String> dict, String sentence) {
// 先将词根都存入 TrieSet
TrieSet set = new TrieSet();
for (String key : dict) {
set.add(key);
}
StringBuilder sb = new StringBuilder();
String[] words = sentence.split(" ");
// 处理句子中的单词
for (int i = 0; i < words.length; i++) {
// 在 Trie 树中搜索最短词根（最短前缀）
String prefix = set.shortestPrefixOf(words[i]);
if (!prefix.isEmpty()) {
// 如果搜索到了，改写为词根
sb.append(prefix);
} else {
// 否则，原样放回
sb.append(words[i]);
}
if (i != words.length - 1) {
// 添加单词之间的空格
sb.append(' ');
}
}
return sb.toString();
}
// 见上文
class TrieSet {}
// 见上文
class TrieMap {}211. 添加与搜索单词 - 数据结构设计
继续看力扣第 211 题「添加与搜索单词 - 数据结构设计」：
211. 添加与搜索单词 - 数据结构设计 | 力扣 | LeetCode |
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
WordDictionary()初始化词典对象void addWord(word)将word添加到数据结构中，之后可以对它进行匹配bool search(word)如果数据结构中存在字符串与word匹配，则返回true；否则，返回false。word中可能包含一些'.'，每个.都可以表示任何一个字母。
示例：
输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]
解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True
提示：
1 <= word.length <= 25addWord中的word由小写英文字母组成search中的word由 '.' 或小写英文字母组成- 最多调用
104次addWord和search
这道题的考点就在于这个 search 函数进行通配符匹配，其实就是我们给 TrieSet 实现的 hasKeyWithPattern 方法，直接套就行了：
class WordDictionary {
TrieSet set = new TrieSet();
// 在 TrieSet 中添加元素
public void addWord(String word) {
set.add(word);
}
// 通配符匹配元素
public boolean search(String word) {
return set.hasKeyWithPattern(word);
}
}
// 见上文
class TrieSet {}
// 见上文
class TrieMap {}上面列举的这几道题用的都是 TrieSet，下面来看看 TrieMap 的题目。
1804. 实现一个 Trie (前缀树 II)
先看力扣第 1804 题「实现前缀树 II」：
1804. 实现 Trie （前缀树） II | 力扣 | LeetCode |
前缀树（trie ，发音为 "try"）是一个树状的数据结构，用于高效地存储和检索一系列字符串的前缀。前缀树有许多应用，如自动补全和拼写检查。
实现前缀树 Trie 类：
Trie()初始化前缀树对象。void insert(String word)将字符串word插入前缀树中。int countWordsEqualTo(String word)返回前缀树中字符串word的实例个数。int countWordsStartingWith(String prefix)返回前缀树中以prefix为前缀的字符串个数。void erase(String word)从前缀树中移除字符串word。
示例 1:
输入
["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"]
[[], ["apple"], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"]]
输出
[null, null, null, 2, 2, null, 1, 1, null, 0]
解释
Trie trie = new Trie();
trie.insert("apple"); // 插入 "apple"。
trie.insert("apple"); // 插入另一个 "apple"。
trie.countWordsEqualTo("apple"); // 有两个 "apple" 实例，所以返回 2。
trie.countWordsStartingWith("app"); // "app" 是 "apple" 的前缀，所以返回 2。
trie.erase("apple"); // 移除一个 "apple"。
trie.countWordsEqualTo("apple"); // 现在只有一个 "apple" 实例，所以返回 1。
trie.countWordsStartingWith("app"); // 返回 1
trie.erase("apple"); // 移除 "apple"。现在前缀树是空的。
trie.countWordsStartingWith("app"); // 返回 0
提示：
1 <= word.length, prefix.length <= 2000word和prefix只包含小写英文字母。insert、countWordsEqualTo、countWordsStartingWith和erase总共调用最多3 * 104次。- 保证每次调用
erase时，字符串word总是存在于前缀树中。
这题就可以用到 TrieMap，每个插入的 word 就是键，插入的次数就是对应的值，然后复用 TrieMap 的 API 就能实现题目要求的这些函数：
class Trie {
// 封装我们实现的 TrieMap
TrieMap<Integer> map = new TrieMap<>();
// 插入 word 并记录插入次数
public void insert(String word) {
if (!map.containsKey(word)) {
map.put(word, 1);
} else {
map.put(word, map.get(word) + 1);
}
}
// 查询 word 插入的次数
public int countWordsEqualTo(String word) {
if (!map.containsKey(word)) {
return 0;
}
return map.get(word);
}
// 累加前缀为 prefix 的键的插入次数总和
public int countWordsStartingWith(String prefix) {
int res = 0;
for (String key : map.keysWithPrefix(prefix)) {
res += map.get(key);
}
return res;
}
// word 的插入次数减一
public void erase(String word) {
int freq = map.get(word);
if (freq - 1 == 0) {
map.remove(word);
} else {
map.put(word, freq - 1);
}
}
}
// 见上文
class TrieMap {}677. 键值映射
反正都是直接套模板，也没什么意思，再看最后一道题目吧，这是力扣第 677 题「键值映射」：
677. 键值映射 | 力扣 | LeetCode |
设计一个 map ，满足以下几点:
- 字符串表示键，整数表示值
- 返回具有前缀等于给定字符串的键的值的总和
实现一个 MapSum 类：
MapSum()初始化MapSum对象void insert(String key, int val)插入key-val键值对，字符串表示键key，整数表示值val。如果键key已经存在，那么原来的键值对key-value将被替代成新的键值对。int sum(string prefix)返回所有以该前缀prefix开头的键key的值的总和。
示例 1：
输入：
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
输出：
[null, null, 3, null, 5]
解释：
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // 返回 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // 返回 5 (apple + app = 3 + 2 = 5)
提示：
1 <= key.length, prefix.length <= 50key和prefix仅由小写英文字母组成1 <= val <= 1000- 最多调用
50次insert和sum
这道题还是标准的 TrieMap 的应用，直接看代码吧：
class MapSum {
// 封装我们实现的 TrieMap
TrieMap<Integer> map = new TrieMap<>();
// 插入键值对
public void insert(String key, int val) {
map.put(key, val);
}
// 累加所有前缀为 prefix 的键的值
public int sum(String prefix) {
List<String> keys = map.keysWithPrefix(prefix);
int res = 0;
for (String key : keys) {
res += map.get(key);
}
return res;
}
}
// 见上文
class TrieMap {}Trie 树这种数据结构的实现原理和题目实践就讲完了，如果你能够看到这里，真得给你鼓掌。纸上得来终觉浅，绝知此事要躬行，我建议最好亲手实现一遍上面的代码，去把题目刷一遍，才能对 Trie 树有更深入的理解。
