共计 3488 个字符，预计需要花费 9 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 648. 单词替换 ，难度为 中等。
Tag :「字典树」
在英语中，咱们有一个叫做 词根(root) 的概念，能够词根前面增加其余一些词组成另一个较长的单词——咱们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其余)，能够造成新的单词 another(另一个)。
当初，给定一个由许多词根组成的词典 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 <= 1000$
- $1 <= dictionary[i].length <= 100$
dictionary[i]仅由小写字母组成。- $1 <= sentence.length <= 10^6$
sentence仅由小写字母和空格组成。sentence中单词的总量在范畴 $[1, 1000]$ 内。sentence中每个单词的长度在范畴 $[1, 1000]$ 内。sentence中单词之间由一个空格隔开。sentence没有前导或尾随空格。
根本剖析
这是一道 Trie 的模板题，还不理解 Trie 的同学能够先看前置 🧀：【设计数据结构】实现 Trie (前缀树)
前置 🧀 通过图解模式解说了 Trie 的构造与原理，以及提供了两种实现 Trie 的形式。
回到本题，为了不便，咱们令 ds 为 dictionary，令 s 为 sentence。
二维数组
一个比拟习惯的做法，是应用「二维数组」来实现 Trie，配合 static 优化，能够无效管制 new 的次数，耗时绝对稳固。
思考两个 Trie 的基本操作：
add操作：变量入参字符串s，将字符串中的每位字符映射到 $[0, 25]$，同时为了可能不便查问某个字符串（而不只是某个前缀）是否已经存入过Trie中，额定应用一个布尔数组isEnd记录某个地位是否为单词结尾。query操作：对变量入参字符串s进行遍历，如果在字典树不存在该字符串的任何前缀，间接返回s，否则返回首个呈现（最短）的前缀。
至于二维数组的大小估算，能够间接开成 $N \times C$，其中 $N$ 为要插入到 Trie 中的字符总数，$C$ 为对应的字符集大小。在 $N \times C$ 没有 MLE 危险时，能够间接开这么多；而当 $N \times C$ 较大（超过 $1e7$，甚至 $1e8$ 时），能够适当将 $N \times C$ 中的 $N$ 缩小，使得总空间在 $1e7$ 左右，因为实际上因为二维数组中的某些行中会存储一个字符以上，实际上咱们用不到这么多行。
代码（不应用 static 优化，耗时减少十倍）：
class Solution {
static int N = 100000, M = 26;
static int[][] tr = new int[N][M];
static boolean[] isEnd = new boolean[N * M];
static int idx;
void add(String s) {
int p = 0;
for (int i = 0; i < s.length(); i++) {int u = s.charAt(i) - 'a';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
}
isEnd[p] = true;
}
String query(String s) {for (int i = 0, p = 0; i < s.length(); i++) {int u = s.charAt(i) - 'a';
if (tr[p][u] == 0) break;
if (isEnd[tr[p][u]]) return s.substring(0, i + 1);
p = tr[p][u];
}
return s;
}
public String replaceWords(List<String> ds, String s) {for (int i = 0; i <= idx; i++) {Arrays.fill(tr[i], 0);
isEnd[i] = false;
}
for (String d : ds) add(d);
StringBuilder sb = new StringBuilder();
for (String str : s.split("")) sb.append(query(str)).append(" ");
return sb.substring(0, sb.length() - 1);
}
}- 工夫复杂度：令 $n = \sum_{i = 0}^{ds.length – 1} ds[i].length$，$m$ 为
s长度，复杂度为 $O(n + m)$ - 空间复杂度：$O(n \times C)$，其中 $C = 26$ 为字符集大小
TrieNode
另外一个可能无效防止「估数组大小」操作的形式，是应用 TrieNode 的形式实现 Trie：每次应用到新的格子再触发 new 操作。
至于为什么有了 TrieNode 的形式，我还是会采纳「二维数组」优先的做法，在 知乎 上有同学问过我相似的问题，只不过原问题是「为什么有了动静开点线段树，间接 build 出 $4n$ 空间的做法仍有意义」，这对应到本题应用「二维数组」还是「TrieNode」是一样的情理：
除非某些语言在启动时，采纳虚拟机的形式，并且事后调配了足够的内存，否则所有的 new 操作都须要反映到 os 上，而在 linux 调配时须要遍历红黑树，因而即便是总空间一样，一次性的 new 要比屡次小空间的 new 更省工夫，同时集中性的 new 也比分散性的 new 操作要更快，这也就是为什么咱们不无脑应用 TrieNode 的起因。
代码：
class Solution {
class Node {
boolean isEnd;
Node[] tns = new Node[26];
}
Node root = new Node();
void add(String s) {
Node p = root;
for (int i = 0; i < s.length(); i++) {int u = s.charAt(i) - 'a';
if (p.tns[u] == null) p.tns[u] = new Node();
p = p.tns[u];
}
p.isEnd = true;
}
String query(String s) {
Node p = root;
for (int i = 0; i < s.length(); i++) {int u = s.charAt(i) - 'a';
if (p.tns[u] == null) break;
if (p.tns[u].isEnd) return s.substring(0, i + 1);
p = p.tns[u];
}
return s;
}
public String replaceWords(List<String> ds, String s) {for (String str : ds) add(str);
StringBuilder sb = new StringBuilder();
for (String str : s.split("")) sb.append(query(str)).append(" ");
return sb.substring(0, sb.length() - 1);
}
}- 工夫复杂度：令 $n = \sum_{i = 0}^{ds.length – 1} ds[i].length$，$m$ 为
s长度，复杂度为 $O(n + m)$ - 空间复杂度：$O(n \times C)$，其中 $C = 26$ 为字符集大小
加餐
明天额定减少一道更贴合口试面试的加餐题 : 联合 DFS 的 Trie 使用题 🎉🎉
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.648 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
