Get all groups of strings that are anagrams (Anagrams)

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

Thoughts:
Anagrams have the same character counts mapping: “ate”, “eat” and “tea” have the same mapping: {‘a’:1, ‘e’:1, ‘t’:1}. So for each string in the group, we treat it as a mapping between chars to ints. If there are n > 1 mappings that are the same, we know there are n anagrams. Therefore our algorithm works this way: in the 1st scan of the group, we build two hash-table: for each string, we connect it with its character counts mapping (this is for later quick reference); for each character counts mapping, we accumulate its count. At the 2nd scan of the group, for each string, we use the 1st hash-table to quickly find its character counts mapping. When we get the mapping, we plug it into the second hash-table and fetch its count, if the count is greater than 1, we know this string is a member of the anagrams so we add it to the solution array. Hence it’s a O(n) algorithm.

Code (Java):

public class Solution {
    public ArrayList<String> anagrams(String[] strs) {
        HashMap<String, HashMap<Character, Integer>> strCharsMap
            = new HashMap<String, HashMap<Character, Integer>>();
        HashMap<HashMap<Character, Integer>, Integer> charsCountMap
            = new HashMap<HashMap<Character, Integer>, Integer>();
        for(String s : strs) {
            HashMap<Character, Integer> map =
                new HashMap<Character, Integer>();
            for(int i = 0; i < s.length(); ++i) {
                char c = s.charAt(i);
                map.put(c, map.get(c) == null ? 1 : map.get(c)+1);
            }
            strCharsMap.put(s, map);
            charsCountMap.put(map, charsCountMap.get(map) == null ?
                                1 : charsCountMap.get(map) + 1);
        }
        
        ArrayList<String> sol = new ArrayList<String>();
        for(String s : strs) {
            if(charsCountMap.get(strCharsMap.get(s)) > 1)
                sol.add(s);
        }
        return sol;
        
    }
}

Code (C++):

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        map<string, map<char, int> > strCharsMap;
        map<map<char, int>, int> charsCountMap;
        for(int i = 0; i < strs.size(); ++i) {
            string s = strs[i];
            map<char, int> map;
            for(int j = 0; j < s.size(); ++j) {
                char c = s[j];
                map[c] += 1;
            }
            strCharsMap[s] = map;
            charsCountMap[map] += 1;
        }
        
        vector<string> sol;
        for(int i = 0; i < strs.size(); ++i) {
            if(charsCountMap[strCharsMap[strs[i]]] > 1)
                sol.push_back(strs[i]);
        }
        return sol;
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: