题目描述
这是 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"提示：
-
dictionary[i]仅由小写字母组成。 
-
sentence仅由小写字母和空格组成。 -
sentence中单词的总量在范围
-
sentence中每个单词的长度在范围
-
sentence中单词之间由一个空格隔开。 -
sentence没有前导或尾随空格。
基本分析
这是一道 Trie 的模板题，还不了解 Trie 的同学可以先看前置 🧀：【设计数据结构】实现 Trie (前缀树)
前置 🧀 通过图解形式讲解了 Trie 的结构与原理，以及提供了两种实现 Trie 的方式。
回到本题，为了方便，我们令 ds 为 dictionary，令 s 为 sentence。
二维数组
一个比较习惯的做法，是使用「二维数组」来实现 Trie，配合 static 优化，可以有效控制 new 的次数，耗时相对稳定。
考虑两个 Trie 的基本操作：
-
add操作：变量入参字符串s，将字符串中的每位字符映射到
，同时为了能够方便查询某个字符串（而不只是某个前缀）是否曾经存入过 Trie中，额外使用一个布尔数组isEnd记录某个位置是否为单词结尾。 -
query操作：对变量入参字符串s进行遍历，如果在字典树不存在该字符串的任何前缀，直接返回s，否则返回首个出现（最短）的前缀。
至于二维数组的大小估算，可以直接开成 
，其中 
为要插入到 Trie 中的字符总数，
为对应的字符集大小。在 没有 MLE 风险时，可以直接开这么多；而当 较大（超过 
，甚至 
时），可以适当将 中的 减少，使得总空间在
代码（不使用 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 ds, String s) {
for (int i = 0; i - 时间复杂度：令
，
为 s长度，复杂度为
- 空间复杂度：
，其中 
TrieNode
另外一个能够有效避免「估数组大小」操作的方式，是使用 TrieNode 的方式实现 Trie：每次使用到新的格子再触发 new 操作。
至于为什么有了 TrieNode 的方式，我还是会采用「二维数组」优先的做法，在 知乎 上有同学问过我类似的问题，只不过原问题是「为什么有了动态开点线段树，直接 build 出 
除非某些语言在启动时，采用虚拟机的方式，并且预先分配了足够的内存，否则所有的 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 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);
}
}- 时间复杂度：令 ， 为
s长度，复杂度为
- 空间复杂度：，其中
加餐
今天额外增加一道更贴合笔试面试的加餐题 : 结合 DFS 的 Trie 运用题 🎉🎉
最后
这是我们「刷穿 LeetCode」系列文章的第 No.648 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
目录 题目地址 代码 Prompt 题目地址 https://ac.nowcoder.com/acm/contest/52826/D 代码 import sys import math def euclidean_distance(p1, p2): retur…
