Algorithms to Group Words by Anagrams


Given an array of strings, group anagrams together.

Example:
Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Output:

1
2
3
4
5
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:
All inputs will be in lowercase.
The order of your output does not matter.

Group Anagrams by using Hash Key

As the words are all lower-case, we can count the frequency of each letter using a static array (e.g. int[26]), thus O(1) constant space. Then we can compute the key for such occurrence.

Then, we group words by same key, at last we push the values one by one to the result array/vector.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        unordered_map<string, vector<string>> data;
        for (const auto &n: strs) {
            data[getKey(n)].push_back(n);
        }
        for (auto it = data.begin(); it != data.end(); ++ it) {
            result.push_back(it->second);
        }
        return result;
    }
private:
    string getKey(const string &s) {
        int cnt[26] = {};
        for (const auto &n: s) {
            cnt[n - 97] ++;
        }
        string r = "";
        for (int i = 0; i < 26; ++ i) {
            r = r + std::to_string(cnt[i]) + ",";
        }
        return r;
    }
};
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        unordered_map<string, vector<string>> data;
        for (const auto &n: strs) {
            data[getKey(n)].push_back(n);
        }
        for (auto it = data.begin(); it != data.end(); ++ it) {
            result.push_back(it->second);
        }
        return result;
    }
private:
    string getKey(const string &s) {
        int cnt[26] = {};
        for (const auto &n: s) {
            cnt[n - 97] ++;
        }
        string r = "";
        for (int i = 0; i < 26; ++ i) {
            r = r + std::to_string(cnt[i]) + ",";
        }
        return r;
    }
};

This approach takes O(N) space as we need a hash map to store the occurence key and the corresponding group of words. The time requirement is O(NM) where M is the average length of the words and N is the length of the word list.

Group Anagrams by Sorting

Anagrams are the same if we sort them. Thus, we can sort each string, and use a hash map to push the same Anagrams to their groups.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:   
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> r;
        unordered_map<string, int> cached;
        for (string n: strs) {
            string t = n;
            sort(n.begin(), n.end());
            if (cached.find(n) != cached.end()) {
                int k = cached[n];
                r[k].push_back(t);
            } else {
                r.push_back({t});
                cached[n] = r.size() - 1;
            }
        }        
        return r;
    }
};
class Solution {
public:   
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> r;
        unordered_map<string, int> cached;
        for (string n: strs) {
            string t = n;
            sort(n.begin(), n.end());
            if (cached.find(n) != cached.end()) {
                int k = cached[n];
                r[k].push_back(t);
            } else {
                r.push_back({t});
                cached[n] = r.size() - 1;
            }
        }        
        return r;
    }
};

This approach takes O(N) space and O(N.MLog(M)) time where N is the input list size and M is the average length of the words.

Another similar implementation to group anagrams by sorting each string:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (auto &str: strs) {
            auto key = str;
            sort(key.begin(), key.end());
            mp[key].push_back(str);
        }
        vector<vector<string>> ans;
        for (auto &[a, b]: mp) {
            ans.push_back(b);
        }
        return ans;
    }
};
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (auto &str: strs) {
            auto key = str;
            sort(key.begin(), key.end());
            mp[key].push_back(str);
        }
        vector<vector<string>> ans;
        for (auto &[a, b]: mp) {
            ans.push_back(b);
        }
        return ans;
    }
};

With Python, shorter code that does the same thing:

1
2
3
4
5
6
7
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
        return list(mp.values())
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
        return list(mp.values())

See also: Teaching Kids Programming – Two Algorithms to Group Anagrams

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
620 words
Last Post: Algorithm to Count the Largest Group of Digit Sums
Next Post: Sum of Multiples of 3 and 5

The Permanent URL is: Algorithms to Group Words by Anagrams

Leave a Reply