HHot 100C++ 图解

49. 字母异位词分组

中等 哈希 在力扣上做

一句话套路排序后的串当分组 key

题目描述

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

 

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释:

  • 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
  • 字符串 "nat" 和 "tan" 是字母异位词,因为它们可以重新排列以形成彼此。
  • 字符串 "ate" ,"eat" 和 "tea" 是字母异位词,因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

 

提示:

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

思路

时间O(n·k log k)
空间O(n·k)

思路

异位词排序后是同一个字符串 —— 拿「排序后的串」当分组 key。

进阶写法

用 26 个字母的计数串做 key(每段前缀一个 '#' 分隔),把每组 O(k log k) 降到 O(k)。分隔符是必需的:没有它,「1个a+11个b」与「11个a+1个b」都会拼成 "111",两组不同字母就被归到一组了。

图解

e 0 a 1 t 2
字符串 eat(来自本仓库测试数据,下标从 0 开始)

C++17 题解

src/01_hash.cpp29 行
namespace lc0049 {
class Solution {
 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (const string& w : strs) {
      string key = w;
      sort(key.begin(), key.end());  // "eat" / "tea" -> "aet"
      groups[key].push_back(w);
    }
    vector<vector<string>> ans;
    ans.reserve(groups.size());
    for (auto& kv : groups) ans.push_back(std::move(kv.second));
    return ans;
  }

  // 计数法 key:适合单词很长、组很多的情况
  static string countKey(const string& w) {
    int cnt[26] = {};
    for (char c : w) cnt[c - 'a']++;
    string key;
    for (int i = 0; i < 26; ++i) {
      key += '#';
      key += std::to_string(cnt[i]);
    }
    return key;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q49_group_anagrams16 行
lc0049::Solution s;
vector<string> a{"eat", "tea", "tan", "ate", "nat", "bat"};
vector<vector<string>> got = s.groupAnagrams(a);
// 组间顺序无序 —— 排序后再比,这是「结果集合类」题目的通用断言手法
for (auto& g : got) sort(g.begin(), g.end());
sort(got.begin(), got.end());
vector<vector<string>> want{{"ate", "eat", "tea"}, {"bat"}, {"nat", "tan"}};
CHECK_EQ(got, want);
// countKey 必须与排序 key 等价
CHECK_EQ(lc0049::Solution::countKey("abc"), lc0049::Solution::countKey("cab"));
// 真正考验 '#' 分隔符的一对:计数序列 [1,11] 与 [11,1],不加分隔都拼成 "111"
const string xa = "a" + string(11, 'b');
const string xb = string(11, 'a') + "b";
CHECK_TRUE(lc0049::Solution::countKey(xa) != lc0049::Solution::countKey(xb));
vector<string> b{""};
CHECK_EQ(s.groupAnagrams(b), vector<vector<string>>{{""}});

↑↓ 选择↵ 打开/ 随时唤起