字母异位词分组
1. 题目
1.1. 描述
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。
1.2. 示例
示例 1
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
示例 2
输入: strs = [“”]
输出: [[“”]]
示例 3
输入: strs = [“a”]
输出: [[“a”]]
1.3. 提示
- 1 <= strs.length <= $10^4$
- 0 <= strs[i].length <= 100
- strs[i] 仅包含小写字母
2. 思路
2.1. 排序
- 将每个字符串字符排序生成新的字符串，按照新字符串为键，字符串为值存入集合中。最后将key对应value输出
- 时间复杂度为O(nlogm)，空间复杂度为O(nm)。n为strs的长度，m为strs中字符串的平均长度
2.2. 哈希
- 将每个字符串字符存入26位数组再生成
#1#0#0...新的字符串，按照新字符串为键，字符串为值存入集合中。最后将key对应value输出
- 时间复杂度为O(nm)，空间复杂度为O(nm)。n为strs的长度，m为strs中字符串的平均长度
3. 代码
3.1. C++
3.1.1. 排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
map<string,vector<string> > matchMap;
vector<vector<string> > ans;
for (int i = 0; i < strs.size(); i++)
{
string str = strs[i];
sort(str.begin(),str.end());
matchMap[str].push_back(strs[i]);
}
for (auto it=matchMap.begin();it!=matchMap.end();it++)
{
ans.push_back(it->second);
}
return ans;
}
};
|
3.1.2. 哈希
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
map<string,vector<string> > matchMap;
vector<vector<string> > ans;
for (int i = 0; i < strs.size(); i++)
{
int alp[26]={0};
string str="";
for (int j = 0; strs[i][j] != '\0'; j++)
{
int temp = strs[i][j]-'a';
alp[temp]++;
}
for (int j = 0; j < 26; j++)
{
str+="#"+to_string(alp[j]);
}
matchMap[str].push_back(strs[i]);
}
for (auto it=matchMap.begin();it!=matchMap.end();it++)
{
ans.push_back(it->second);
}
return ans;
}
};
|
3.2. Java
3.2.1. 排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> existMap = new HashMap<>();
for (String str : strs) {
char s[] = str.toCharArray();
Arrays.sort(s);
String temp = new String(s);
if(existMap.get(temp)==null){
List<String> alist = new ArrayList<>();
alist.add(str);
existMap.put(temp, alist);
}else{
existMap.get(temp).add(str);
}
}
return new ArrayList<>(existMap.values());
}
}
|
3.2.2. 哈希
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> existMap = new HashMap<>();
for (String str : strs) {
char[] ss = str.toCharArray();
int[] nums=new int[26];
Arrays.fill(nums, 0);
for (char s : ss) {
nums[s-'a']++;
}
String temp = "";
for (int i = 0; i < 26; i++) {
temp+="#"+nums[i];
}
if(existMap.get(temp)==null){
List<String> alist = new ArrayList<>();
alist.add(str);
existMap.put(temp, alist);
}else{
existMap.get(temp).add(str);
}
}
return new ArrayList<>(existMap.values());
}
}
|