题目对应LeetCode648. 单词替换
1. 题目描述
在英语中，我们有一个叫做 词根(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”
2. 题解
2.1 字典树介绍
这是一道「字典树」的模板题，下面介绍字典树：
「字典树」数据结构一般用于判断是否具有相同前缀，因此非常适合用来解决当前题。
字典树结构：
1
2
3
4
5
6
7
8
9
| class Trie {
boolean isEnd;
Trie[] children;
public Trie() {
children = new Trie[len];
isEnd = false;
}
}
|
其一般包含两个属性：
isEnd：标识当前字典树节点是否对应单词的最后字符children：子节点数组，数组长度取决于字符种类数，一般情况，对于只包含小写字母的字典树，子数组长度一般为26
2.2 字典树解法
字典树算法主要包括两个步骤：
- 建树
建立一颗包含所有词根的字典树，代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public void build(Trie root, String str) {
Trie cur = root;
for (int i=0; i<str.length(); i++) {
int idx = str.charAt(i) - 'a';
if (cur.children[idx] == null) {
cur.children[idx] = new Trie();
}
cur = cur.children[idx];
}
cur.isEnd = true;
}
}
class Trie {
Trie[] children;
boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
}
|
下图展示了词根数组[abc, cb]建树过程：
- 搜索
找出一个单词的最短词根，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public String check(String s, Trie root) {
Trie cur = root;
for (int i=0; i<s.length(); i++) {
int idx = s.charAt(i) - 'a';
if (cur.children[idx] == null) {
return s;
}
cur = cur.children[idx];
if (cur.isEnd) {
return s.substring(0, i+1);
}
}
return s;
}
|
2.3 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
Trie root = new Trie();
for (String str : dictionary) {
build(root, str);
}
StringBuilder builder = new StringBuilder();
String[] arr = sentence.split(" ");
for (int i=0; i<arr.length; i++) {
String str = check(arr[i], root);
builder.append(str);
if (i != arr.length - 1) {
builder.append(" ");
}
}
return builder.toString();
}
public String check(String s, Trie root) {
Trie cur = root;
for (int i=0; i<s.length(); i++) {
int idx = s.charAt(i) - 'a';
if (cur.children[idx] == null) {
return s;
}
cur = cur.children[idx];
if (cur.isEnd) {
return s.substring(0, i+1);
}
}
return s;
}
public void build(Trie root, String str) {
Trie cur = root;
for (int i=0; i<str.length(); i++) {
int idx = str.charAt(i) - 'a';
if (cur.children[idx] == null) {
cur.children[idx] = new Trie();
}
cur = cur.children[idx];
}
cur.isEnd = true;
}
}
class Trie {
Trie[] children;
boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
}
|
复杂度分析
- 时间复杂度：
O(d + s)。其中 d 为dictionary的字符数，s 是sentence的字符数。构建字典树时间复杂度为O(d)，每个单词搜索前缀均为线性时间复杂度。
- 空间复杂度：
O(d)，搜索树的复杂度，即为dictionary的字符数。
运行结果：
