题目描述

这是 LeetCode 上的 「677. 键值映射」 ，难度为 「中等」。

Tag : 「字典树」、「DFS」、「哈希表」

实现一个 MapSum 类，支持两个方法，insert和sum：

  • MapSum() 初始化 MapSum 对象
  • void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
  • int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

示例：

输入：
["MapSum","insert","sum","insert","sum"]
[[],["apple",3],["ap"],["app",2],["ap"]]

输出：
[null,null,3,null,5]

解释：
MapSummapSum=newMapSum();
mapSum.insert("apple",3);
mapSum.sum("ap");//return3(apple=3)
mapSum.insert("app",2);
mapSum.sum("ap");//return5(apple+app=3+2=5)

提示：

  • key 和 prefix 仅由小写英文字母组成
  • 1 <= val <= 1000
  • 最多调用 50 次 insert 和 sum

Trie + DFS

从需要实现「存储字符串（映射关系）」并「检索某个字符串前缀的总和」来看，可以知道这是与 相关的题目，还不了解 的同学可以先看前置 ：实现 Trie (前缀树) 。

考虑如何实现两个操作：

  • insert ：在基本的 插入操作的基础上进行拓展即可。与常规的插入操作的唯一区别为，不能简单记录单词的结束位置，还要存储 对应的 是多少。具体的我们可以使用 int 类型的数组 来代替原有的 boolean 类型的数组 ；

  • sum ： 先对入参 进行字典树搜索，到达尾部后再使用 DFS 搜索后面的所有方案，并累加结果。

代码（static 优化代码见 ，避免每个样例都 new 大数组）：

classMapSum{
int[][]tr=newint[2510][26];
int[]hash=newint[2510];
intidx;
publicvoidinsert(Stringkey,intval){
intp=0;
for(inti=0;i<key.length();i++){
intu=key.charAt(i)-'a';
if(tr[p][u]==0)tr[p][u]=++idx;
p=tr[p][u];
}
hash[p]=val;
}
publicintsum(Stringprefix){
intp=0;
for(inti=0;i<prefix.length();i++){
intu=prefix.charAt(i)-'a';
if(tr[p][u]==0)return0;
p=tr[p][u];
}
returndfs(p);
}
intdfs(intp){
intans=hash[p];
for(intu=0;u<26;u++){
if(tr[p][u]!=0)ans+=dfs(tr[p][u]);
}
returnans;
}
}
classMapSum{
staticint[][]tr=newint[2510][26];
staticint[]hash=newint[2510];
staticintidx;
publicMapSum(){
for(inti=0;i<=idx;i++)Arrays.fill(tr[i],0);
Arrays.fill(hash,0);
idx=0;
}
publicvoidinsert(Stringkey,intval){
intp=0;
for(inti=0;i<key.length();i++){
intu=key.charAt(i)-'a';
if(tr[p][u]==0)tr[p][u]=++idx;
p=tr[p][u];
}
hash[p]=val;
}
publicintsum(Stringprefix){
intp=0;
for(inti=0;i<prefix.length();i++){
intu=prefix.charAt(i)-'a';
if(tr[p][u]==0)return0;
p=tr[p][u];
}
returndfs(p);
}
intdfs(intp){
intans=hash[p];
for(intu=0;u<26;u++){
if(tr[p][u]!=0)ans+=dfs(tr[p][u]);
}
returnans;
}
}
  • 时间复杂度：令 的最大长度为 ，最大调用次数为 ，字符集大小为 （ 本题 固定为 ）， insert 操作的复杂度为 ；从 DFS 的角度分析， sum 操作的复杂度为 ，但事实上，对于本题具有明确的计算量上界，搜索所有的格子的复杂度为
  • 空间复杂度：

Trie 记录前缀字符串总和

为降低 sum 操作的复杂度，我们可以在 insert 操作中同时记录（累加）每个前缀的总和。

代码（static 优化代码见 ，避免每个样例都 new 大数组）：

classMapSum{
intN=2510;
int[][]tr=newint[N][26];
int[]hash=newint[N];
intidx;
Mapmap=newHashMap();
publicvoidinsert(Stringkey,intval){
int_val=val;
if(map.containsKey(key))val-=map.get(key);
map.put(key,_val);
for(inti=0,p=0;i<key.length();i++){
intu=key.charAt(i)-'a';
if(tr[p][u]==0)tr[p][u]=++idx;
p=tr[p][u];
hash[p]+=val;
}
}
publicintsum(Stringprefix){
intp=0;
for(inti=0;i<prefix.length();i++){
intu=prefix.charAt(i)-'a';
if(tr[p][u]==0)return0;
p=tr[p][u];
}
returnhash[p];
}
}
classMapSum{
staticintN=2510;
staticint[][]tr=newint[N][26];
staticint[]hash=newint[N];
staticintidx;
staticMapmap=newHashMap();
publicMapSum(){
for(inti=0;i<=idx;i++)Arrays.fill(tr[i],0);
Arrays.fill(hash,0);
idx=0;
map.clear();
}
publicvoidinsert(Stringkey,intval){
int_val=val;
if(map.containsKey(key))val-=map.get(key);
map.put(key,_val);
for(inti=0,p=0;i<key.length();i++){
intu=key.charAt(i)-'a';
if(tr[p][u]==0)tr[p][u]=++idx;
p=tr[p][u];
hash[p]+=val;
}
}
publicintsum(Stringprefix){
intp=0;
for(inti=0;i<prefix.length();i++){
intu=prefix.charAt(i)-'a';
if(tr[p][u]==0)return0;
p=tr[p][u];
}
returnhash[p];
}
}
  • 时间复杂度：令 的最大长度为 ， insert 操作的复杂度为 ； sum 操作的复杂度为
  • 空间复杂度：令 的最大长度为 ，最大调用次数为 ，字符集大小为 （ 本题 固定为 ），复杂度为

最后

这是我们「刷穿 LeetCode」系列文章的第 No.677 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地

本文由 mdnice 多平台发布