Algorithms to Group Words by Anagrams

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

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

推荐阅读：
子产论尹何为邑原文及翻译　 子产坏晋馆垣原文及翻译　 季札观周乐/季札观乐原文及翻译　 百家讲坛系列节目《汉代风云人物》MP3蓝奏云下载　 晏子不死君难原文及翻译　 子产告范宣子轻币原文及翻译　 祁奚请免叔向原文及翻译　 驹支不屈于晋原文及翻译　 吕相绝秦原文及翻译　 诗词名句鉴赏：一顾倾人城，再顾倾人国。　
评论列表
添加评论