49. 字母异位词分组
#leetcode#hash 2025-02-01

Problem: 49. 字母异位词分组

解析

分组的依据是异位词，要找到异位词相同的东西key，将异位词放入对应的key中。这样就可以将异位词分组了。

排序取字典

将每个字符串排序后，放入字典中，key是排序后的字符串，value是原字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//！n*klog(k),n*k -> 排序耗时是n个klog(k),k是strs中字符串的平均长度；空间复杂度不算返回值的话主要哈希表的存储
class Solution {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> hashTable;

    for (int i = 0; i < strs.size(); ++i) {
      string key = strs[i];
      sort(key.begin(), key.end());
      hashTable[key].emplace_back(strs[i]);
    }
    vector<vector<string>> res;
    for (auto e : hashTable) {
      res.emplace_back(e.second);
    }

    return res;
  }
};

计数取字典

不用sort方法，用计数法来确认唯一的key

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
//! n*k, n*k -> 遍历strs中每个字符串的长度耗时；空间复杂度不算返回值的话主要哈希表的存储
class Solution {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> res;
    unordered_map<string, vector<string>> hashTable;
    for (auto e : strs) {
      array<int, 26> asc = {0};
      for (int i = 0; i < e.size(); ++i) {
        ++asc[e[i] - 'a'];
      }
      string temp;
      for (int i = 0; i < asc.size(); ++i) {
        temp += to_string(asc[i]) + '#';
      }

      hashTable[temp].emplace_back(e);
    }

    for (auto e : hashTable) {
      res.emplace_back(e.second);
    }
    return res;
  };
};