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 <= 1040 <= strs[i].length <= 100strs[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",两组不同字母就被归到一组了。
图解
字符串
eat(来自本仓库测试数据,下标从 0 开始)C++17 题解
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;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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>>{{""}});