C++, Easy solution, ordered map


  • 7
    Z
    class MapSum {
    public:
        /** Initialize your data structure here. */    
        void insert(string key, int val) {
            mp[key] = val;
        }
        
        int sum(string prefix) {
            int sum = 0, n = prefix.size();
            for (auto it = mp.lower_bound(prefix); it != mp.end() && it->first.substr(0, n) == prefix; it++) 
                sum += it->second;
            return sum;
        }
    private:
        map<string, int> mp;
    };
    

  • 0
    R

    Neat. No need to reinvent the wheel.


  • 0
    Z

    @rizkaz Thanks! Although Trie is better for performance


  • 0
    R

    @zestypanda Hard to say for sure without knowing the nature of the input data and overhead caused by sub-optimal implementations. But yeah, interviewers are probably looking for a 'trie' answer here.


  • 0
    A

    @zestypanda Using unordered_map ran faster for me (i.e. only 3ms). It depends on the data of course. unordered_set insertions are faster always. Look-ups are mixed. Overall I think unordered_set might be better.


  • 0
    Z

    @algorithmic It is a trade-off. For unordered_map, sum is O(n), insert is O(1); For map, insert is O(logn), sum is O(logn+k), k is total valid words.
    In summary, the worst case for unordered_map is O(n), for map is O(log n). So in real world and interviews, map is better. But Trie is best.


  • 0
    V

    @rizkaz said in C++, Easy solution, ordered map:

    trie

    One can break out of map much early. Map keys are sorted, so if we find prefix once, we can break out if map key does not have prefix.


Log in to reply
 

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