49. Group Anagrams

2020, Nov 26 2 mins read

1. Description

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

2. Example

Example 1

Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]
Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
Explanation:

There is no string in strs that can be rearranged to form “bat”.
The strings “nat” and “tan” are anagrams as they can be rearranged to form each other.
The strings “ate”, “eat”, and “tea” are anagrams as they can be rearranged to form each other.

Example 2

Input: strs = [""]
Output: [[""]]

Example 3

Input: strs = [“a”]
Output: [[“a”]]

3. Constraints

1 <= strs.length <= 10$^{4}$
0 <= strs[i].length <= 100
strs[i] consists of lower-case English letters.

4. Solutions

Hash Table

n = strs.size(), k is the string size in strs

Time complexity : O(nk)
Space complexity : O(nk)

 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
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<string>> groupAnagrams(const vector<string> &strs) {
        const int n = strs.size();
        unordered_map<array<int, 26>, vector<string>, array_hash> anagrams;
        for (const string &str : strs) {
            array<int, 26> count{};
            for (char c : str) {
                ++count[c - 'a'];
            }

            anagrams[count].emplace_back(str);
        }

        vector<vector<string>> groups;
        for (auto &[count, group] : anagrams) {
            groups.push_back(move(group));
        }

        return groups;
    }

private:
    struct array_hash {
        size_t operator()(const array<int, 26> &a) const {
            size_t h = 0;
            for (int x : a) {
                h ^= hash<int>{}(x) + 0x9e3779b9 + (h << 6) + (h >> 2);
            }

            return h;
        }
    };
};

Search

Tags