0001-0100 - 0049-字母异位词分组 - 《LeetCode》

题目链接
题目描述
示例
- 示例1：
提示
思路
- 思路1：排序+哈希表
- 思路2：哈希映射优化
题解
复杂度分析

题目链接

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

示例

示例1：

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

提示

1 <= strs.length <= 10
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

思路

思路1：排序+哈希表
如果两个字符串是字母异位词，那么它们排序后的字符串是相同的，可以将排序后的字符串作为哈希表的键值。

思路2：哈希映射优化
最朴素的想法就是将字母与其出现的次数转为字符串作为键值，如 abandon 转成 a2b1d1n2o1 ，但此方法会有大量的时间开销。
考虑两种常见的哈希函数：移位异或和素数乘法
移位异或将计数数组作为键，在c++中，需要重写哈希函数（不同语言的操作不同，如Python将 list 转成 tuple 即可）。

素数乘法存在溢出的问题，这可以通过模一个较大的素数解决，但可能会导致碰撞。

题解

思路1：排序+哈希表

class Solution {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
      unordered_map<string, vector<string>> mp;
      vector<vector<string>> ans;
      for (string& str : strs) {
          string key = str;
          sort(key.begin(), key.end());
          mp[key].emplace_back(str);
      }
      for (auto& i : mp) {
          ans.emplace_back(i.second);
      }
      return ans;
  }
};

思路2：负优化（笑

class Solution {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
      unordered_map<string, vector<string>> mp;
      vector<vector<string>> ans;
      for (string& str : strs) {
          int count[26] = {0};
          for (char c : str) {
              ++count[c - 'a'];
          }
          string key;
          for (int i = 0; i < 26; ++i) {
              if (count[i]) {
                  key.push_back(i + 'a');
                  key.append(to_string(count[i]));
              }
          }
          mp[key].emplace_back(str);
      }

      for (auto& i : mp) {
          ans.emplace_back(i.second);
      }

      return ans;
  }
};

思路2：移位异或

class Solution {
 public:
  struct hashFunc {
      size_t operator()(const array<int, 26>& arr) const {
          return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
              return (acc << 1) ^ hash<int>()(num);
          });
      }
  };
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
      unordered_map<array<int, 26>, vector<string>, hashFunc> mp;
      vector<vector<string>> ans;
      for (string& str : strs) {
          array<int, 26> counts{};
          int length = str.length();
          for (int i = 0; i < length; ++i) {
              counts[str[i] - 'a']++;
          }
          mp[counts].emplace_back(str);
      }
      for (auto& i : mp) {
          ans.emplace_back(i.second);
      }

      return ans;
  }
};

思路2：素数乘法

class Solution {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
      unordered_map<double, vector<string>> mp;
      vector<vector<string>> ans;
      double prime[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
      for (string& str : strs) {
          double key = 1;
          for (char c : str) {
              key *= prime[c - 'a'];
          }
          mp[key].emplace_back(str);
      }

      for (auto& i : mp) {
          ans.emplace_back(i.second);
      }
      return ans;
  }
};

复杂度分析

0049-字母异位词分组 - 图1 是 0049-字母异位词分组 - 图2 中的字符串的数量， 0049-字母异位词分组 - 图3 是 0049-字母异位词分组 - 图4 中的字符串的的最大长度， 0049-字母异位词分组 - 图5 是字符集，在本题中字符集为所有小写字母， 0049-字母异位词分组 - 图6 。