题目形容
这是 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 多平台公布