Algorithms to Group Words by Anagrams

  • 时间：2020-10-11 15:48:46
  • 分类：网络文摘
  • 阅读：143 次

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.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
数学题:前三轮的平均的平均分是94　 数学题:财务室会计结账时，发现账面上少了890.1元钱　 数学题:一个玻璃瓶内原有盐是水的1/11　 数学题:把圆柱平均分成若干份后拼成一个长方体　 奥数题:甲乙两地中间有一座山岭　 奥数题:一份工作按计划的时间算　 简便计算题：1997÷(1997+1997/1998)+(1/1999)　 数学题:在比例尺1：5000的图纸上　 2014年是平年还是闰年　 数学题:在11次红灯变绿灯之间的黄灯亮起中　
评论列表
添加评论