leetcode 677. Map Sum Pairs | 677. 键值映射（Trie前缀树，BFS）

柔情只为你懂 2022-08-29 06:18 100阅读 0赞

## 题目 ##

[https://leetcode.com/problems/map-sum-pairs/][https_leetcode.com_problems_map-sum-pairs]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

基于前缀树实现，可以参考：[leetcode 208. Implement Trie (Prefix Tree) | 208. 实现 Trie 前缀树（Java）][leetcode 208. Implement Trie _Prefix Tree_ _ 208. _ Trie _Java] 中的数据结构，然后加以改造即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]  
上代码。其中，insert() 函数的四个分类 `存在 不存在 末尾 非末尾` 是需要注意的细节。

class Node { 
        Node[] map;
        int[] value;
    
        public Node() { 
            this.map = new Node['z' - 'a' + 1];
            this.value = new int['z' - 'a' + 1];
        }
    
        public Node getNode(char c) { 
            return map[c - 'a'];
        }
    
        public int getValue(char c) { 
            return value[c - 'a'];
        }
    
        public Node put(char c, int val) {  // 新建node，会破坏后续节点
            Node node = new Node();
            map[c - 'a'] = node;
            value[c - 'a'] = val;
            return node;
        }
    
        public Node set(char c, int val) {  // 仅覆盖value，保留后续节点
            value[c - 'a'] = val;
            return map[c - 'a'];
        }
    }
    
    class MapSum { 
        Node node;
    
        /** * Initialize your data structure here. */
        public MapSum() { 
            node = new Node();
        }
    
        public void insert(String key, int val) { 
            Node cur = node;
            for (int i = 0; i < key.length(); i++) { 
                if (cur.getNode(key.charAt(i)) != null) {  // 存在
                    if (i == key.length() - 1) {  // 末尾
                        cur = cur.set(key.charAt(i), val);
                    } else {  // 非末尾
                        cur = cur.getNode(key.charAt(i));
                    }
                } else {  // 不存在
                    if (i == key.length() - 1) {  // 末尾
                        cur = cur.put(key.charAt(i), val);
                    } else {  // 非末尾
                        cur = cur.put(key.charAt(i), 0);
                    }
                }
            }
        }
    
        public int sum(String prefix) { 
            Node cur = node;
            int sum = 0;
            for (int i = 0; i < prefix.length(); i++) { 
                if (cur.getNode(prefix.charAt(i)) == null) {  // 走投无路，匹配失败
                    return 0;
                } else { 
                    if (i == prefix.length() - 1) {  // 当前字母是prefix的结尾字母
                        sum = cur.getValue(prefix.charAt(i));
                    }
                    cur = cur.getNode(prefix.charAt(i));
                }
            }
            return dfs(cur, sum);
        }
    
        public int dfs(Node node, int sum) { 
            for (int i = 0; i < node.map.length; i++) { 
                if (node.map[i] != null) { 
                    sum += node.value[i];
                    sum = dfs(node.map[i], sum);
                }
            }
            return sum;
        }
    }
    
    /** * Your MapSum object will be instantiated and called as such: * MapSum obj = new MapSum(); * obj.insert(key,val); * int param_2 = obj.sum(prefix); */

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_map-sum-pairs]: https://leetcode.com/problems/map-sum-pairs/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/c8fcfa91e8494cfc96e78707c2e8dbe5.png
[leetcode 208. Implement Trie _Prefix Tree_ _ 208. _ Trie _Java]: https://blog.csdn.net/sinat_42483341/article/details/117767824
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/fb94a74ae8a24538b88f8aacfc200eba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20220829/1837da9b11fa4eaf8cbab95b111699da.png