[LeetCode] Anagrams

Problem Statement (link):

Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.

Analysis:
How to determine if two strings are anagrams?

My first thought was to store each chars from the first string in a hash map, then probe the hash map with each chars in the second string to determine if two strings have the sames chars. If we use this approach, we need to make sure we consider the duplication cases. We could potentially use the value field in the hash map to record the number of occurrence of each char. The time complexity is O(m), where m is the length of the string. The implementation is provided at the end of this post

The second idea is to simply sort string 1, and compare it with the sorted string 2, if they are equal, it means these two are anagrams. The time complexity of this algorithm is O(m log m), which is worse than the first one where we use hash map. However, it turned out that this idea suits this problem better as we have to probe another hash map that stores all strings every time a new string comes in in order to determine if the incoming string is anagram with any of the existing strings in the hash map, this leads to a O(m*n^2) algorithm in general.

The overall time complexity of the second approach is O(n * m log m). Where n is the number of strings and m is the average string length.

Code:

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> out;
        if (strs.empty()) return out;
        unordered_map<string, int> map;

        for (int i=0; i<strs.size(); i++) {
            string tmp=strs[i];
            sort(tmp.begin(), tmp.end());

            if (map.find(tmp)!=map.end()) { // found
                out.push_back(strs[i]);
                // insert the 1st occurance string if hvn't done it
                if (map[tmp]>=0) { 
                    out.push_back(strs[map[tmp]]);
                    map[tmp]=-1;
                }
            }
            else
                map.emplace(tmp, i);
        }
        return out;
    }
};

Takeaways:
- A better partial solution doesn't necessarily lead to a better overall solution.

Here is the code for checking if two strings are anagrams using a hash map, assuming the strings are legal.

bool isAnagram(string a, string b) {
    unordered_map<char, int> map;

    // construct map using string a
    for (int i=0; i<a.size(); i++) {
        if (map.find(a[i]) == map.end())
            map.emplace(a[i], 1);
        else
            map[a[i]]++;
    }

    // check anagram using the map
    for (int i=0; i<b.size(); i++) {
        if (map.find(b[i])==map.end() || map[b[i]]<1)
            return false;
        else
            map[b[i]]--;
    }

    // check map if all value is 0
    for (unordered_map<char, int>::iterator it=map.begin(); it!=map.end(); it++)
        if (it->second!=0)
            return false;
    return true;
}