Leetcode 677. Map Sum Pairs

题目

解法：

使用前缀树或者字典树
每个节点代表一个字母，利用map来储存相邻字符之间的关系
这个题还需要后续深入理解

struct TrieNode
{
    TrieNode* child[26] = {
    };int sum = 0;
};class MapSum {
    
public:TrieNode trieRoot;unordered_map<string,int> map_;void insert(string key, int val) {
    int diff = val - map_[key];TrieNode* curr = &trieRoot;for(auto c : key){
    c = c - 'a';if(curr->child[c] == nullptr) curr->child[c] = new TrieNode();curr = curr->child[c];curr->sum += diff;}map_[key] = val;}int sum(string prefix) {
    TrieNode* curr = &trieRoot;for(auto c : prefix){
    c = c - 'a';if(curr->child[c] == nullptr) return 0;curr = curr->child[c];}return curr->sum;}
};

class TrieNode:def __init__(self):self.child = collections.defaultdict(TrieNode)self.sum = 0
class MapSum:def __init__(self):self.trieRoot = TrieNode()self.map_ = collections.defaultdict(int)def insert(self, key: str, val: int) -> None:curr = self.trieRootdiff = val - self.map_[key]for c in key:curr = curr.child[c]curr.sum += diffself.map_[key] = valdef sum(self, prefix: str) -> int:curr = self.trieRootfor c in prefix:if c not in curr.child:return 0curr = curr.child[c]return curr.sum

参考：
https://leetcode.com/problems/map-sum-pairs/discuss/1371761/C%2B%2BJavaPython-Trie-and-HashMap-Efficient-and-Clean-and-Concise