[C++] Simple code using unordered_multimap.


  • 2
    S

    I'm sharing my C++ code using unordered_multimap. Actually, I haven't used unordered_multimap before so I had to learn how to use it. First, the difference between unordered_map and unordered_multimap is that the latter supports multiple values to be stored with the same key.

    I found these links useful to learn how to iterate through multi map.
    http://stackoverflow.com/questions/9046922/c-unordered-multimap
    http://stackoverflow.com/questions/19716202/boost-unordered-multimap-loop-over-the-unique-keys

    The most essential function in using unordered_multimap is the equal_range() function. It gives iterator to elements from the first and the last+1 th element with the query key. Note also, we need to be careful on how we iterate over unique keys without using extra storage.

    Since this is my first time using this container, I might be very suboptimal. I'm open to any suggestions to make the code more elegant and readable.

    class Solution {
    public:
        vector<string> anagrams(vector<string> &strs) {
    
            vector<string> result;
            unordered_multimap<string, string> dict;
            
            // put everything into multimap
            for (int i=0; i<strs.size(); i++){
                string key = strs[i];
                sort(key.begin(), key.end());
                dict.insert( {key, strs[i]} );
            }
            
            // loop over unique keys
            for (auto iter=dict.begin(); iter!=dict.end(); iter=dict.equal_range(iter->first).second){
                auto unique_key = iter->first;
                if (dict.count(unique_key) > 1){ // if count is greater than 1, push the values to the result.
                    auto it_bounds = dict.equal_range(unique_key);
                    for (auto it=it_bounds.first; it!=it_bounds.second; it++){
                        result.push_back(it->second);
                    }
                }
            }
            return result;
        }
    };
    

  • 2
    J

    Good to see the multimap version. You don't need to use strs[i] as the second value, just i is enough.

    I've modified your code to suit my taste. :p

    class Solution {
    public:
        vector<string> anagrams(vector<string> &strs) {
            vector<string> result;
            if (strs.size() < 2) return result;
            unordered_multimap<string, int> collections;
            for (int i = 0; i < strs.size(); i++){
                string s = strs[i];
                sort(s.begin(), s.end());
                collections.insert({s, i});
            }
            auto it = collections.begin();
            while (it != collections.end()) {
                string s = it->first;
                if (collections.count(s) > 1) {
                    auto range = collections.equal_range(s);
                    for (auto it = range.first; it != range.second; it++){
                        result.push_back(strs[it->second]);
                    }
                }
                it = collections.equal_range(s).second;
            }
            return result;
        }
    };
    

    And here is my one-pass unordered_map version.

    class Solution {
    public:
        vector<string> anagrams(vector<string> &strs) {
            vector<string> result;
            if (strs.size() < 2) return result;
            unordered_map<string, int> cache;
            for (int i = 0; i < strs.size(); i++) {
                string s = strs[i];
                sort(s.begin(), s.end());
                auto it = cache.find(s);
                if (it == cache.end()) {
                    cache[s] = i;
                } else {
                    result.push_back(strs[i]);
                    if (it->second >= 0) {
                        result.push_back(strs[it->second]);
                        it->second = -1;
                    }
                }
            }
            return result;
        }
    };

  • 0
    J

    BTW, if I remove if (dict.count(unique_key) > 1){, it will get Output Limit Exceeded. Seems like a bug of gcc.


Log in to reply
 

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