LeetCode- Map Sum Pairs Solution

目录隐藏

题目：

Implement a MapSum class with insert, and sum methods.

For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.

Example 1:

Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5

实现：

蛮力解法：已字符串为key和计数为value创建HashMap，进行sum 时遍历HashMap，如果该键以给定的前缀开头，则进行累计。时间复杂度 O(N), 空间复杂度O(N)


class MapSum {
    
    private HashMap<String, Integer> map;
    /** Initialize your data structure here. */
    public MapSum() {
        map = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        map.put(key, val);
    }
    
    public int sum(String prefix) {
        int ans = 0;
        for (String key: map.keySet()){
            if (key.startsWith(prefix)){
                ans += map.get(key);
            }
        }
        
        return ans;
    }
}

前缀hash：单独创建一个SumMap存放前缀所有出现的累计值，当插入键值对时Map，SumMap记录所有前缀子串的值val，如果插入键值对已存在。 SumMap记录其变化值 val – map.getOrDefault(key, 0)。时间复杂度 O(N), 空间复杂度O(N)

class MapSum {
    
    private Map <String, Integer> map;
    private Map <String, Integer> summap;
   
    public MapSum() {
        map = new HashMap<>();
        summap = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        String prefix = "";
        for (char c: key.toCharArray()){
            prefix += c;
            summap.put(prefix, summap.getOrDefault(prefix, 0)+delta);
        }
    }
    
    public int sum(String prefix) {
       
        return summap.getOrDefault(prefix, 0);
    }
}

Trie： Tire节点中增加一个计数器即可, 流程与上一个解法一致。

class TrieNode {
         Map<Character, TrieNode> children = new HashMap();
         Integer score = new Integer(0);
}

class MapSum {
    
    private  TrieNode root;
    private  Map<String, Integer> map;
   
    public MapSum() {
        root = new TrieNode();
        map = new HashMap();
    }
    
    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode cur = root;
        cur.score += delta;
        for (char c: key.toCharArray()){
            cur.children.putIfAbsent(c, new TrieNode());
            cur = cur.children.get(c);
            cur.score += delta;
        }
    }
    
    public int sum(String prefix) {
       
        TrieNode cur = root;
        for (char c: prefix.toCharArray()){
            cur = cur.children.get(c);
            if (cur == null ){
                return 0;
            }
        }
        return cur.score;
    }
    
  
}

参考及引用：

https://leetcode.com/problems/map-sum-pairs/solution/

Photo by Steve Johnson from Pexels

LeetCode- Map Sum Pairs Solution

题目：

实现：

参考及引用：

garlic