字母异位词分组
题目描述
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。题目链接
示例 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"]]
解题思路
首先这一题先要理解题目意思：对于每一个字符串，如果这个字符串中的各个字母出现的次数是相同的（位置顺序可以不同），那么这些字符串就是字母异位词，需要将这些字符串分在同一个组别之中。
理解了题目意思之后，问题就在于怎样判断两个字符串是否是字母异位词。
解法一：排序 + 哈希表
第一种想法就是将每个字符串都按字典序排序，即可判断。 不过你需要保存原字符串（因为最终输出的是原字符串），所以可以用 unordered_map<string,vector<string>> 来存储：
- 键：排序后的字符串
- 值：原字符串列表
这样字母异位词的字符串就自动分在同一组了。
复杂度分析
- 时间复杂度：
O
(
n
k
log
k
)
O(nk\\log k)
O(nklogk) - 空间复杂度：
O
(
n
k
)
O(nk)
O(nk) 其中n
n
n 是字符串数量，k
k
k 是所有字符串中的最大长度。
代码实现
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for(auto &e: strs){
string temps = e;
sort(temps.begin(),temps.end());
mp[temps].push_back(e);
}
vector<vector<string>> ans;
for(auto &e: mp){
ans.push_back(e.second);
}
return ans;
}
};
解法二：字符计数法（优化时间复杂度）
第二种想法：因为第一种思路需要将字符串进行排序，时间复杂度会变高。 按理说要判断两个字符串是否是异位词，只需要扫描一遍即可
O
(
k
)
O(k)
O(k)，不用排序（排序最快也是
O
(
k
log
k
)
O(k\\log k)
O(klogk)）。
而一个字符串仅由 26 个小写英文字母组成，所以我们只需要统计每个字符串每个字母出现的次数即可。 （按顺序统计，比如 abc 就是 1,1,1,0,0,…0，acd 就是 1,0,1,1,0,…0）
然后在判断的时候用数组标记是否已经被加入结果，已经被加入则直接跳过，这样时间复杂度就是
O
(
n
k
)
O(nk)
O(nk)。
代码实现
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
int n = strs.size();
vector<vector<int>> a(n,vector<int>(26,0));
for(int i = 0; i<n; i++){
for(int j = 0; strs[i][j]; j++){
a[i][strs[i][j] – 'a']++;
}
}
vector<vector<string>> ans;
vector<int> fg(n,1);
for(int i = 0; i<n; i++){
if(fg[i] == 0) continue;
vector<string> res;
res.push_back(strs[i]);
fg[i] = 0;
for(int j = i+1; j<n; j++){
int k = 0;
while(k<26 && a[i][k] == a[j][k]) k++;
if(k == 26){
res.push_back(strs[j]);
fg[j] = 0;
}
}
ans.push_back(res);
}
return ans;
}
};
每日心灵鸡汤
深耕细作，久久为功；点滴积累，终成星河。
