给你一个长度为 n 的数组 words ，该数组由 非空 字符串组成。
定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。
- 例如，如果
words = ["a", "ab", "abc", "cab"] ，那么 "ab" 的分数是 2 ，因为 "ab" 是 "ab" 和 "abc" 的一个前缀。
返回一个长度为 __n 的数组 __answer __ ，其中 __answer[i] __ 是 _ _words[i]
的每个非空前缀的分数 总和 。
注意： 字符串视作它自身的一个前缀。
示例 1：
**输入：** words = ["abc","ab","bc","b"]
**输出：** [5,4,3,2]
**解释：** 对应每个字符串的答案如下：
- "abc" 有 3 个前缀："a"、"ab" 和 "abc" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" ，1 个字符串的前缀为 "abc" 。
总计 answer[0] = 2 + 2 + 1 = 5 。
- "ab" 有 2 个前缀："a" 和 "ab" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" 。
总计 answer[1] = 2 + 2 = 4 。
- "bc" 有 2 个前缀："b" 和 "bc" 。
- 2 个字符串的前缀为 "b" ，1 个字符串的前缀为 "bc" 。
总计 answer[2] = 2 + 1 = 3 。
- "b" 有 1 个前缀："b"。
- 2 个字符串的前缀为 "b" 。
总计 answer[3] = 2 。
示例 2：
**输入：** words = ["abcd"]
**输出：** [4]
**解释：**
"abcd" 有 4 个前缀 "a"、"ab"、"abc" 和 "abcd"。
每个前缀的分数都是 1 ，总计 answer[0] = 1 + 1 + 1 + 1 = 4 。
提示：
1 <= words.length <= 10001 <= words[i].length <= 1000words[i] 由小写英文字母组成
208. 实现 Trie (前缀树)
648. 单词替换
211. 添加与搜索单词 - 数据结构设计
677. 键值映射
676. 实现一个魔法字典
745. 前缀和后缀搜索
6183. 字符串的前缀分数和
如果只想看本题的解法，可直接跳到文章末尾，有详细分析过程！！🔥🔥🔥
「前缀树」又叫「字典树」或「单词查找树」，总之它们是一个意思！
「前缀树」的应用场景：给定一个字符串集合构建一棵前缀树，然后给一个字符串，判断前缀树中是否存在该字符串或者该字符串的前缀
可以结合题目 单词替换 理解！我们需要根据 dictionary 构建前缀树，然后判断 sentence 中的每个单词是否在前缀树中
分析
一般而言，字符串的集合都是仅由小写字母构成，所以本文章都是基于该情况展开分析！
字符串集合：[them, zip, team, the, app, that]。这个样例的前缀树长什么样呢？
由于都是小写字母，所以对于每个节点，均有 26 个孩子节点，上图中没有画出来，省略了而已…，但是要记住：每个节点均有 26 个孩子节点
还有一个点要明确：节点仅仅表示从根节点到本节点的路径构成的字符串是否有效而已
对于上图中橙色的节点，均为有效节点，即：从根节点到橙色节点的路径构成的字符串均在集合中
如果现在要找前缀 te 是否存在，分两步：
- 首先看看表示
te 字符串的路径是否存在，这个例子是存在的
- 其次看看该路径的终点处的节点是否有效，很遗憾，此处为白色，无效
- 所以前缀
te 不存在！！
数据结构
现在看看如何表示这棵「前缀树」，即数据结构该如何定义。其实就是一棵多叉树，有 26 个孩子节点的多叉树而已！！
现在来思考节点的值又该如何表示呢？
在上面的例子中，节点仅仅表示路径构成的字符串是否有效而已，所以节点可以用 boolean 类型来表示
还有一类情况就是每个字符串都有一个权值，所以节点的值可以用一个数值来表示
1
2
3
4
5
6
7
|
class TrieNode {
boolean val;
TrieNode[] children = new TrieNode[26];
}
private TrieNode root = new TrieNode();
|
常用操作
根据上面的分析，其实「前缀树」常用操作就三种
- 根据所给字符串集合构建前缀树
- 判断前缀树中是否存在目标字符串
- 在前缀树中找出目标字符串的最短前缀
构建前缀树
最初，我们只有一个根节点 root，孩子节点也都还没初始化！
所以直接看代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public void insert(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) p.children[i] = new TrieNode();
p = p.children[i];
}
p.val = true;
}
|
为了扩展思维，这里再给出递归的实现方法：(和树的遍历很像)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public TrieNode insert(TrieNode node, String word, int index) {
if (node == null) node = new TrieNode();
if (index == word.length()) {
node.val = true;
return node;
}
int i = word.charAt(index) - 'a';
node.children[i] = insert(node.children[i], word, index + 1);
return node;
}
root = insert(root, word, 0);
|
寻找目标字符串
当「前缀树」构建好了后，寻找目标字符串也就大同小异了
复习一下寻找的两个步骤：
- 首先看看表示字符串的路径是否存在
- 其次看看该路径的终点处的节点是否有效
1
2
3
4
5
6
7
8
9
10
11
| public boolean query(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) return false;
p = p.children[i];
}
return p.val;
}
|
同样的，为了扩展思维，这里再给出递归的实现方法：(和树的遍历很像)
1
2
3
4
5
6
7
8
9
10
11
| public boolean query(TrieNode node, String word, int index) {
if (node == null) return false;
if (index == word.length()) return node.val;
int i = word.charAt(index) - 'a';
return query(node.children[i], word, index + 1);
}
query(root, word, 0);
|
寻找最短前缀
和「寻找目标字符串」差不多，但又有些许不同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public String shortestPrefixOf(String word) {
TrieNode p = root;
StringBuffer sb = new StringBuffer();
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.val) return sb.toString();
sb.append(c);
if (p.children[i] == null) return "";
p = p.children[i];
}
return "";
}
|
高级操作
含有通配符的寻找
顾名思义，.可以表示任何字符。比如：a.c 是可以和 [abc, aec] 匹配的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public boolean keysWithPattern(TrieNode node, String pattern, int index) {
if (node == null) return false;
if (index == key.length()) return node.val;
int i = key.charAt(index) - 'a';
if (key.charAt(index) == '.') {
for (int j = 0; j < 26; j++) {
if (search(node.children[j], key, index + 1)) return true;
}
return false;
} else {
return search(node.children[i], key, index + 1);
}
}
|
题目实战
实现 Trie (前缀树)
题目详情可见 实现 Trie (前缀树)
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
| class Trie {
class TrieNode {
boolean val;
TrieNode[] children = new TrieNode[26];
}
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) p.children[i] = new TrieNode();
p = p.children[i];
}
p.val = true;
}
public boolean search(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) return false;
p = p.children[i];
}
return p.val;
}
public boolean startsWith(String prefix) {
TrieNode p = root;
for (char c : prefix.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) return false;
p = p.children[i];
}
return true;
}
}
|
单词替换
题目详情可见 单词替换
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
| class Solution {
class TrieNode {
boolean val;
TrieNode[] children = new TrieNode[26];
}
private TrieNode root = new TrieNode();
public String replaceWords(List<String> dictionary, String sentence) {
for (String d : dictionary) root = insert(root, d, 0);
StringBuffer ans = new StringBuffer();
for (String s : sentence.split(" ")) {
String q = query(s);
if ("".equals(q)) ans.append(s).append(" ");
else ans.append(q).append(" ");
}
ans.deleteCharAt(ans.length() - 1);
return ans.toString();
}
private TrieNode insert(TrieNode node, String key, int index) {
if (node == null) node = new TrieNode();
if (index == key.length()) {
node.val = true;
return node;
}
int i = key.charAt(index) - 'a';
node.children[i] = insert(node.children[i], key, index + 1);
return node;
}
private String query(String key) {
TrieNode p = root;
StringBuffer ans = new StringBuffer();
for (char c : key.toCharArray()) {
int i = c - 'a';
if (p.val) return ans.toString();
ans.append(c);
if (p.children[i] == null) return "";
p = p.children[i];
}
return "";
}
}
|
添加与搜索单词 - 数据结构设计
题目详情可见 添加与搜索单词 - 数据结构设计
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
| class WordDictionary {
class TrieNode {
boolean val;
TrieNode[] children = new TrieNode[26];
}
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) p.children[i] = new TrieNode();
p = p.children[i];
}
p.val = true;
}
public boolean search(String word) {
return search(root, word, 0);
}
private boolean search(TrieNode node, String key, int index) {
if (node == null) return false;
if (index == key.length()) return node.val;
int i = key.charAt(index) - 'a';
if (key.charAt(index) == '.') {
for (int j = 0; j < 26; j++) {
if (search(node.children[j], key, index + 1)) return true;
}
return false;
} else {
return search(node.children[i], key, index + 1);
}
}
}
|
键值映射
题目详情可见 键值映射
这个题目些许不同，每个节点表示的不再是是否有效，而是一个值
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
| class MapSum {
class TrieNode {
int val;
TrieNode[] children = new TrieNode[26];
}
private TrieNode root;
public MapSum() {
root = new TrieNode();
}
public void insert(String key, int val) {
TrieNode p = root;
for (char c : key.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) p.children[i] = new TrieNode();
p = p.children[i];
}
p.val = val;
}
public int sum(String prefix) {
TrieNode p = root;
for (char c : prefix.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) return 0;
p = p.children[i];
}
return getAllSum(p);
}
private int getAllSum(TrieNode node) {
if (node == null) return 0;
int sum = 0;
for (int i = 0; i < 26; i++) {
sum += getAllSum(node.children[i]);
}
return sum + node.val;
}
}
|
实现一个魔法字典
题目详情可见 实现一个魔法字典
由于本题目必须替换一次，所以采取了一个傻办法：遍历每一种替换的情况
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
| class MagicDictionary {
class TrieNode {
boolean val;
TrieNode[] children = new TrieNode[26];
}
private TrieNode root;
public MagicDictionary() {
root = new TrieNode();
}
public void buildDict(String[] dictionary) {
for (String word : dictionary) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) p.children[i] = new TrieNode();
p = p.children[i];
}
p.val = true;
}
}
public boolean search(String searchWord) {
for (int i = 0; i < searchWord.length(); i++) {
if (search(root, searchWord, 0, i)) return true;
}
return false;
}
private boolean search(TrieNode node, String searchWord, int index, int changeId) {
if (node == null) return false;
if (index == searchWord.length()) return node.val;
int i = searchWord.charAt(index) - 'a';
if (index == changeId) {
for (int j = 0; j < 26; j++) {
if (j == i) continue;
if (search(node.children[j], searchWord, index + 1, changeId)) return true;
}
return false;
}
return search(node.children[i], searchWord, index + 1, changeId);
}
}
|
前缀和后缀搜索
题目详情可见 前缀和后缀搜索
前面的题目，节点表示的要么是有效性，要么是字符串的权值，而这个题目需要从前缀和后缀同时搜索 🔍
我们的可以采取的思路：同时维护两棵树 -> 「前缀树」和「后缀树」，树的每个节点表示以「从根节点到该节点路径构成的字符串」为前缀的单词的下标
表述的可能比较抽象，直接看图：(我们还是以 [them, zip, team, the, app, that] 这个样例为基础)
当我们需要寻找以 t 为前缀，以 m 为后缀的下标最大的字符串
显然我们可以很容易找到图中绿色的两个节点，对应的下标 List 为 [0, 2, 3, 5] 和 [0, 2]
解释：以 t 为前缀的单词有 [them, team, the, that]，其对应的下标为 [0, 2, 3, 5]
同理：以 m 为后缀的单词有 [them, team]，其对应的下标为 [0, 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
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
| class WordFilter {
class TrieNode {
List<Integer> list = new ArrayList<>();
TrieNode[] children = new TrieNode[26];
}
private TrieNode prefix = new TrieNode();
private TrieNode suffix = new TrieNode();
public WordFilter(String[] words) {
build(prefix, words, true);
build(suffix, words, false);
}
public int f(String pref, String suff) {
List<Integer> prefList = query(prefix, pref, true);
List<Integer> suffList = query(suffix, suff, false);
int i = prefList.size() - 1, j = suffList.size() - 1;
while (i >= 0 && j >= 0) {
int l1 = prefList.get(i), l2 = suffList.get(j);
if (l1 == l2) return l1;
else if (l1 > l2) i--;
else j--;
}
return -1;
}
private void build(TrieNode root, String[] words, boolean isPref) {
for (int i = 0; i < words.length; i++) {
TrieNode p = root;
int len = words[i].length();
for (int j = isPref ? 0 : len - 1; j >= 0 && j < len; j = isPref ? j + 1 : j - 1) {
int cur = words[i].charAt(j) - 'a';
if (p.children[cur] == null) p.children[cur] = new TrieNode();
p = p.children[cur];
p.list.add(i);
}
}
}
private List<Integer> query(TrieNode root, String s, boolean isPref) {
TrieNode p = root;
int len = s.length();
for (int i = isPref ? 0 : len - 1; i >= 0 && i < len; i = isPref ? i + 1 : i - 1) {
int cur = s.charAt(i) - 'a';
if (p.children[cur] == null) return new ArrayList<>();
p = p.children[cur];
}
return p.list;
}
}
|
字符串的前缀分数和
题目详情可见 前缀和后缀搜索
这个题也是「前缀树」的模版题，只不过每个节点的含义需要重新定义一下：表示以该路径为前缀的单词数量
可能表述的有些抽象，以 ["abc","ab","bc","b"] 为例，直接看图：
构建好了前缀树，如果我们需要查询某个单词的前缀分数和，如 "abc"，只需要路径 abc 的节点累加即可，2 + 2 + 1 = 5
下面给出代码：
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
| public int[] sumPrefixScores(String[] words) {
for (String word : words) {
insert(word);
}
int[] ans = new int[words.length];
for (int i = 0; i < words.length; i++) {
ans[i] = query(words[i]);
}
return ans;
}
class TrieNode {
int val;
TrieNode[] children = new TrieNode[26];
}
private TrieNode root = new TrieNode();
public void insert(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) p.children[i] = new TrieNode();
p.children[i].val += 1;
p = p.children[i];
}
}
public int query(String word) {
TrieNode p = root;
int cnt = 0;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.children[i] == null) return cnt;
p = p.children[i];
cnt += p.val;
}
return cnt;
}
|
