49. Group Anagrams

Posted on Edited on In

49. Group Anagrams

Description

Difficulty: Medium

Related Topics: Array, Hash Table, String, Sorting

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

1
2
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

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

Example 3:

1
2
Input: strs = ["a"]
Output: [["a"]]

Constraints:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Hints/Notes

  • 2023/12/19
  • encode the string, use map to record strings with the same encoding
  • 0x3F’s solution(checked)

Solution

Language: C++

Cleaner solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> m;
        for (string str : strs) {
            string sorted_str = str;
            ranges::sort(sorted_str);
            m[sorted_str].push_back(str);
        }
        vector<vector<string>> res;
        for (auto& [_, v] : m) {
            res.push_back(v);
        }
        return res;
    }
};
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
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> m;
        for (string str : strs) {
            string encode = encodeStr(str);
            m[encode].push_back(str);
        }
        vector<vector<string>> res;
        for (auto it = m.begin(); it != m.end(); it++) {
            res.push_back(it->second);
        }
        return res;
    }

    string encodeStr(string str) {
        int count[26] = {0};
        for (char c : str) {
            count[c - 'a']++;
        }
        string s;
        for (int i = 0; i < 26; i++) {
            s += to_string(count[i]);
            s.push_back('a' + i);
        }
        return s;
    }
};