Algorithms to Group Words by Anagrams

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

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

推荐阅读：
Backpacking Problem Variation via Greedy Approach: How Many Appl　 Sliding Window to Get Equal Substrings Within MaxCost Budget　 Beginner’s Guide to Python’ Enumerate Function　 Algorithms to Determine Unique Number of Occurrences　 The Next Permutation Algorithm in C++ (std::next_permutation)　 Binary Tree Zigzag Level Order Traversal Algorithms using DFS an　 Work-Life Balance Tips to Keep You Happy as a Blogger　 Huffington Post Launches New Contributor System And Bloggers Are　 5 Tips for a Smooth Transition When Moving Your Blog to a New Ho　 Jerusalem To Host The Biggest Travel Blogging Event In The World　
评论列表
添加评论