Algorithms to Group Words by Anagrams

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

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) —

推荐阅读：
高纤维饼干口感好是靠油脂“润滑”　 所谓非油炸蔬果干食品同样不健康　 儿童不宜吃含化学合成甜味剂的食品　 规范使用食品添加剂不危害人体健康　 消费者对保健食品不要盲目的迷恋　 广西已暂停销售多个品牌保健食品　 无公害蔬菜如何用感官简单进行识别　 食品安全危机期，谁来保障吃的安全？　 夏季熬制“开花”绿豆汤防暑又解毒　 炎炎夏日如何制作生津止渴的酸梅汤　
评论列表
添加评论