LeetCode 677. 键值映射
原题链接
中等
作者:
我是java同学
,
2023-10-14 22:06:12
,
所有人可见
,
阅读 42
class MapSum {
public:
struct Node {
int val;
Node *son[26];
Node() {
val = 0;
for (int i = 0; i < 26; i ++ )
son[i] = NULL;
}
}* root;
MapSum() {
root = new Node();
}
void insert(string key, int val) {
auto p = root;
for (auto c: key) {
int u = c - 'a';
if (!p->son[u]) p->son[u] = new Node();
p = p->son[u];
}
p->val = val;
}
int sum(string prefix) {
auto p = root;
for (int i = 0; i < prefix.size(); i ++ ) {
int u = prefix[i] - 'a';
if (!p->son[u]) return 0;
p = p->son[u];
}
return dfs(p);
}
int dfs(Node* p) {
if (!p) return 0;
int ans = p->val;
for (int i = 0; i < 26; i ++ )
ans += dfs(p->son[i]);
return ans;
}
};
/**
* Your MapSum object will be instantiated and called as such:
* MapSum* obj = new MapSum();
* obj->insert(key,val);
* int param_2 = obj->sum(prefix);
*/