【leetcode】【剑指offer Ⅱ】066. 单词之和

问题描述：

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

核心思路：

• 该题仍然是前缀树应用题。
  • insert 函数相当于往前缀树中插入单词，在单词的结尾更新 val。
  • sum 函数相当于在前缀树中搜索前缀 prefix，如果没有路径可以走完 prefix，则说明前缀树中没有单词具有前缀 prefix，此时返回 0 即可；如果走完 prefix，则继续递归访问，获得当前节点所在子树的所有节点值。

代码实现：

class Trie
{
public:
    vector<Trie*> next;
    int val;
    Trie() : next(26, nullptr), val(0) {}
};

class MapSum
{
private:
    Trie* root;
    int dfs(Trie* cur)
    {
        if(!cur) return 0;
        int ans = cur->val;
        for(int i = 0; i < 26; ++i)
            ans += dfs(cur->next[i]);
        return ans;
    }
public:
    /** Initialize your data structure here. */
    MapSum()
    {
        root = new Trie();
    }
    
    void insert(string key, int val)
    {
        Trie* cur = root;
        for(char& c : key)
        {
            if(!cur->next[c-'a']) cur->next[c-'a'] = new Trie();
            cur = cur->next[c-'a'];
        }
        cur->val = val;
    }
    
    int sum(string prefix)
    {
        Trie* cur = root;
        for(char& c : prefix)
        {
            if(!cur->next[c-'a']) return 0;
            cur = cur->next[c-'a'];
        }
        return dfs(cur);
    }
};
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