leetcode：49. 字母异位词分组

题目

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

提示：strs[i] 仅包含小写字母

示例：

  1. 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
  2. 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
  1. 输入: strs = [""]
  2. 输出: [[""]]
  1. 输入: strs = ["a"]
  2. 输出: [["a"]]

解答 & 代码

两个单词是字母异位词，当且仅当两个字符串包含的字母相同。

解法一：单词内部排序

两个单词是字母异位词，等价于两个字符串包含的字母相同，也等价于两个单词内部分别排序后得到的字符串相等。
因此，可以先分别将每个单词内部排序。设置一个哈希表，将排序后的字符串作为哈希表的 key，字母异位词数组作为 value。

  1. class Solution {
  2. public:
  3.     vector<vector<string>> groupAnagrams(vector<string>& strs) {
  4.           // 哈希表，key=单词内部排序后的字符串，value=对应的字母异位词数组
  5.         unordered_map<string, vector<string>> map;
  6.           // 遍历单词数组，分别排序，并存入哈希表
  7.         for(int i = 0; i < strs.size(); ++i)
  8.         {
  9.             string sorted_str = strs[i];
  10.               // sort 头文件：#include <algorithm>
  11.             sort(sorted_str.begin(), sorted_str.end());
  12.             if(map.find(sorted_str) == map.end())
  13.                 map[sorted_str] = (vector<string>){strs[i]};
  14.             else
  15.                 map[sorted_str].push_back(strs[i]);
  16.         }
  18.           // 将哈希表的结果存储到结果数组
  19.         vector<vector<string>> resultList;
  20.         for(auto it = map.begin(); it != map.end(); ++it)
  21.             resultList.push_back(it->second);
  22.         return resultList;
  23.     }
  24. };

复杂度分析：设 strs 长度（即单词数量为 n），单词最大长度为 k

  • 时间复杂度 O(nklogk)：每个单词排序时间复杂度 O(klogk)，n 个单词需要排序
  • 空间复杂度 O(nk)：需要用哈希表存储全部字符

执行结果：

  1. 执行结果：通过
  3. 执行用时：20 ms, 在所有 C++ 提交中击败了 98.36% 的用户
  4. 内存消耗：19.1 MB, 在所有 C++ 提交中击败了 63.02% 的用户

解法二：单词内部字符计数

解法一是将单词内部排序后的字符串作为哈希表的 key，也可以将单词内部字符计数作为哈希表的 key

  1. class Solution {
  2. public:
  3.     vector<vector<string>> groupAnagrams(vector<string>& strs) {
  4.         // 哈希表：
  5.         // - key=单词内部字符的计数，string 类型，存储 26 个英文小写字母出现的次数
  6.         // - value=对应的字母异位词数组
  7.         unordered_map<string, vector<string>> map;
  8.         // 遍历单词数组，分别对单词的字符计数，并存入哈希表
  9.         for(int i = 0; i < strs.size(); ++i)
  10.         {
  11.             // 对单词 strs[i] 的字符计数
  12.             string key(26, '0');
  13.             for(int j = 0; j < strs[i].size(); ++j)
  14.                 ++key[strs[i][j] - 'a'];
  15.             // 存入哈希表
  16.             if(map.find(key) == map.end())
  17.                 map[key] = (vector<string>){strs[i]};
  18.             else
  19.                 map[key].push_back(strs[i]);
  20.         }
  22.         // 将哈希表的结果存储到结果数组
  23.         vector<vector<string>> resultList;
  24.         for(auto it = map.begin(); it != map.end(); ++it)
  25.             resultList.push_back(it->second);
  26.         return resultList;
  27.     }
  28. };

复杂度分析：设 strs 长度（即单词数量为 n），单词最大长度为 k，字符集 Σ（这里是26个小写字母）

  • 时间复杂度 O(nk)：每个单词计数时间复杂度 O(k)，n 个单词需要计数
  • 空间复杂度 [中等] 49. 字母异位词分组 - 图1：需要用哈希表存储全部字符，时间复杂度 nk；而最坏情况下每个单词都需要一个字符串来记录每个字母的出现次数，时间复杂度 [中等] 49. 字母异位词分组 - 图2

执行结果：

  1. 执行结果：通过
  3. 执行用时：40 ms, 在所有 C++ 提交中击败了 25.61% 的用户
  4. 内存消耗：21 MB, 在所有 C++ 提交中击败了 14.54% 的用户