LC.P677[键值映射]

LC.P677[键值映射]

方法一：Trie+DFS

class MapSum {

    Trie trie;

    public MapSum() {
        trie = new Trie();
    }

    public void insert(String key, int val) {
        trie.insert(key, val);
    }

    public int sum(String prefix) {
        Trie node = trie;
        for (int i = 0; i < prefix.length(); ++i) {
            int u = prefix.charAt(i) - 'a';
            if (node.next[u] == null) return 0;
            node = node.next[u];
        }
        return dfs(node);
    }

    private int dfs(Trie node) {
        if (node == null) return 0;
        int ans = node.val;
        for (Trie child : node.next) {
            ans += dfs(child);
        }
        return ans;
    }

    private static class Trie {
        Trie[] next;
        int val;

        public Trie() {
            next = new Trie[26];
            val = 0;
        }

        public void insert(String word, int val) {
            Trie node = this;
            for (int i = 0; i < word.length(); ++i) {
                int u = word.charAt(i) - 'a';
                if (node.next[u] == null) {
                    node.next[u] = new Trie();
                }
                node = node.next[u];
            }
            node.val = val;
        }
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

方法二：哈希表

class MapSum {
    
    Map<String, Integer> map;

    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 s : map.keySet()) {
            if (s.startsWith(prefix)) {
                ans += map.get(s);
            }
        }
        return ans;
    }
}