C++ O(1) 9 lines, Trie + Hash map


  • 2
    V

    Hash map is to locate existing values, and trie is store the prefixes sum. Technically, the runtime complexity is affected by the size of individual strings, but here we can say O(1) as the string size is limited to 100.

    struct trie { trie* ch[26] = {}; int sum = 0; } root;
    unordered_map<string, int> pairs;
    void insert(string key, int val) {
        auto p = &root;
        for (auto i = 0; i < key.size(); p->sum += val - pairs[key], ++i) 
            p = p->ch[key[i] - 'a'] = p->ch[key[i]  - 'a'] == nullptr ? new trie() : p->ch[key[i] - 'a'];
        pairs[key] = val;
    }
    int sum(string prefix) {
        auto p = &root;
        for (auto i = 0; i < prefix.size() && p != nullptr; p = p->ch[prefix[i] - 'a'], ++i) ;
        return p == nullptr ? 0 : p->sum;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.