My O(N*M*logM) one pass C++ solution


  • 2
    J

    It's easy to understand. :)

    While looping through the words, it hashes the words into sorted strings and use this string as a key to store the index of the first word of every anagram group.

    All anagrams in a group will use the same key, e.g. dog and god are both sorted into dgo, loop and pool to loop. Then the later words can check if there is an anagram for it.

    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]);
                    // Don't forget to collect the first anagram in the group!
                    if (it->second >= 0) {
                        result.push_back(strs[it->second]);
                        it->second = -1;  // no duplicates
                    }
                }
            }
            return result;
        }
    };
    

    At last, can you find a better hashing technique (get the same key for every anagrams in a group) and replace std::sort to make a O(n*m) algorithm and use less memory for the cache? (Yeah, I know one.)


  • 0

    Although your code seems concise and self explanatory, please add at least a few brief sentences about the general thoughts. For example, why is it concise compared to other solutions?

    Your contribution is greatly appreciated by the rest of the community. Thanks!


  • 0
    J

    OK. I've elaborated my solution. :)


Log in to reply
 

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