LeetCode 677. 键值映射 特里树题解，对比粗暴解、特里树解法。
677. 键值映射#
https://leetcode.cn/problems/map-sum-pairs/
设计一个 map ，满足以下几点:
- 字符串表示键，整数表示值
- 返回具有前缀等于给定字符串的键的值的总和
实现一个 MapSum 类：
- MapSum() 初始化 MapSum 对象
- void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对 key-value 将被替代成新的键值对。
- int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
Trie#
本题求解 sum(prefix) 本质上需要记录（或者计算）每个前缀对应信息。前缀操作符合Trie的特性。
同时题干要求 insert(k,v) 时需更新键对应值，因为还需要一个map维护kv关系。
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
/*
* 设：
* n 为入参字符串长度
* m 为插入的字符串数量
*/
static class Trie {
/*
* 执行用时：
* 12 ms
* , 在所有 Java 提交中击败了
* 25.64%
* 的用户
* 内存消耗：
* 41.7 MB
* , 在所有 Java 提交中击败了
* 7.29%
* 的用户
* 通过测试用例：
* 35 / 35
*/
/**
* 特里树根
* 空间占用 O(n*m)
*/
Node root;
/**
* 记录每个key最新value，方便后续替换
* 空间占用 O(m)
*/
Map<String, Integer> kv;
public Trie() {
root = new Node();
kv = new HashMap<>();
}
/**
* 插入时间复杂度：O(n)
*/
void insert(String key, int val) {
Node curr = root;
char[] arr = key.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (!curr.children.containsKey(arr[i])) {
curr.children.put(arr[i], new Node());
}
// 求和
curr.children.get(arr[i]).sum += val;
// 将原来已存在的值删掉
if (kv.containsKey(key)) {
curr.children.get(arr[i]).sum -= kv.get(key);
}
curr = curr.children.get(arr[i]);
}
kv.put(key, val);
}
Node findNodeByPrefix(String prefix) {
Node curr = root;
char[] arr = prefix.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (!curr.children.containsKey(arr[i])) {
curr.children.put(arr[i], new Node());
}
curr = curr.children.get(arr[i]);
}
return curr;
}
/**
* sum时间复杂度：O(n)
*/
int sum(String prefix) {
Node node = findNodeByPrefix(prefix);
return node == null ? -1 : node.sum;
}
/**
* 前缀树节点
*/
class Node {
/**
* 上下级
*/
Map<Character, Node> children;
/**
* 前缀求和
*/
int sum;
public Node() {
this.children = new HashMap<>();
this.sum = 0;
}
}
}
|
复杂度分析#
insert：插入复杂度只跟单词长度有关，为O(n)。sum：求和依旧是沿着特里树查找，O(n)。
额外使用一个map维护kv映射，占用m个空间。
额外使用了TrieNode维护前缀信息，占用小于n*m，插入单词前缀重复越多，效率越高。
综合空间复杂度O(n*m)。
粗暴遍历#
使用一个map维护kv映射。
求前缀和时，逐个查找、匹配。
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
|
/**
* 执行用时：
* 11 ms
* , 在所有 Java 提交中击败了
* 63.95%
* 的用户
* 内存消耗：
* 41.2 MB
* , 在所有 Java 提交中击败了
* 64.71%
* 的用户
* 通过测试用例：
* 35 / 35
* <p>
* 粗暴查找
*/
static class BF {
/**
* 存每个key对应数值
* 空间占用 O(m)
*/
Map<String, Integer> kv;
public BF() {
kv = new HashMap<>();
}
/**
* 时间复杂度取决于hashmap.put复杂度，为 O(1)
*/
void insert(String key, int val) {
kv.put(key, val);
}
/**
* 时间复杂度取决于 key数量*key长度，为 O(m*n)
*/
int sum(String prefix) {
int sum = 0;
for (Map.Entry<String, Integer> entry : kv.entrySet()) {
if (entry.getKey().startsWith(prefix)) {
sum += entry.getValue();
}
}
return sum;
}
}
|
复杂度分析#
insert：插入复杂度与hashmap.put有关，为O(1)。sum：求和先遍历每个kv，其次遍历单个prefix的长度，O(m*n)。
额外使用一个map维护kv映射，占用m个空间。
空间复杂度O(m)。
可以看到特里树的解法用例效果不是很好，在有限用例的情况下，特里树的前缀重用取决于入参单词的数据特征，因此实际工程中需衡量。
理论上特里树的时间效率只取决于单个单词、前缀的长短，表现会很稳定。