每日一题一一Leetcode49.-字母异位词分组
目录
每日一题一一Leetcode49. 字母异位词分组
每日一题一一Leetcode49. 字母异位词分组
作者：blue
时间：2025.3.11
题目链接：
解法一（超时）：本题要将所有相同字母组成的字符串，存储到同一个集合，然后最后放到一个大集合中返回，我的思路是遍历每一个未被加入集合的字串，然后判断后面的字串是否与其构成变为词，整体代码时间复杂度为 O ( n 2∗ k l o g k )
class Solution {
public:
bool check(string src,string dest){
if(src.size()!=dest.size()) return false;
vector<char> vec_src;
vector<char> vec_dest;
for(int i=0;i<src.size();i++) vec_src.push_back(src[i]);
for(int i=0;i<dest.size();i++) vec_dest.push_back(dest[i]);
sort(vec_src.begin(),vec_src.end());
sort(vec_dest.begin(),vec_dest.end());
for(int i=0;i<vec_src.size();i++){
if(vec_src[i]!=vec_dest[i]) return false;
}
return true;
}
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
vector<int> Hash(strs.size(),0);
for(int i=0;i<strs.size();i++){
if(Hash[i]==0){//还没有被归化
Hash[i]=1;
vector<string> minres;
minres.push_back(strs[i]);
for(int j=i+1;j<strs.size();j++){
if(check(strs[i],strs[j])){
minres.push_back(strs[j]);
Hash[j]=1;
}
}
res.push_back(minres);
}
}
return res;
}
};解法二：优化解法
- 使用哈希表
：借助
unordered_map<string, vector<string>>来存储排序后的字符串及其对应的变位词组。 - 遍历字符串数组 ：针对每个字符串，先复制一份并对其进行排序，接着把原字符串添加到排序后字符串对应的变位词组中。
- 提取结果
：遍历哈希表，将每个变位词组添加到最终结果
result里。
通过使用哈希表来优化，将时间复杂度降低到 O ( n ∗ k l o g k )。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string,vector<string>> map;
for(string s : strs){
string scopy = s;
sort(s.begin(),s.end());//以排序后的字符串为键，没排序的为值
map[s].push_back(scopy);
}
for(auto pair : map){//直接取每个键的值即可
res.push_back(pair.second);
}
return res;
}
};Java代码优化解法：
import java.util.*;
public class Day01_demo49 {
public static void main(String[] args) {
String[] str = {"eat", "tea", "tan", "ate", "nat", "bat"};
List<List<String>> lists = groupAnagrams(str);
for (List<String> list : lists) {
System.out.println(list);
}
}
public static List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, ArrayList<String>> map = new HashMap<>();
for (String str : strs) {
char[] charArrays = str.toCharArray();//先变成字符数组
Arrays.sort(charArrays);//后对字符数组进行排序
String KeyStr = new String(charArrays);//够造出键
// 使用 computeIfAbsent 方法，如果键不存在则创建一个新的 ArrayList
map.computeIfAbsent(KeyStr, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(map.values());
}
}