My simple O(n*m*log(m)) solution with unordered_map


  • 0
    Z
    class Solution {
    public:
        vector<string> anagrams(vector<string> &strs) {
            vector<string> result;
            if (strs.empty()) return result;
            vector<string> tmp(strs);
            unordered_map<string, int, hash<string> > hashmap;
            for (int i = 0; i < strs.size(); i++) {
                sort(strs[i].begin(), strs[i].end());
                if (hashmap.find(strs[i]) == hashmap.end()) hashmap.insert(pair<string, int>(strs[i], -i-1)); //make sure the key value of the first insert is negative
                else {
                    int cur = hashmap.find(strs[i]) -> second;
                    if (cur < 0) { // if the key value is negative, also need to push the original one to the result vector
                        result.push_back(tmp[-1 - cur]);
                        hashmap.find(strs[i]) -> second = -1 - cur;
                    }
                    result.push_back(tmp[i]);
                }
            }
            return result;
        }
    };

  • 4
    L

    Indeed, it is O(n * m * log(m)) time. I think unordered_map can be used in a simpler way.

    class Solution {
    public:
        vector<string> anagrams(vector<string> &strs) {
            unordered_map<string, vector<string> > v;
            for (const auto & str : strs) {
                string s = str;
                sort(s.begin(), s.end());
                v[s].push_back(str);
            }
            vector<string> ans;
            for (auto p : v) {
                if (p.second.size() > 1)
                    ans.insert(ans.end(), p.second.begin(), p.second.end());
            }
    
            return move(ans);
        }
    };

Log in to reply
 

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