给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串
https://leetcode-cn.com/problems/group-anagrams/
示例1：
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
提示：
所有输入均为小写字母。
不考虑答案输出的顺序。
Java解法
思路：
- 因为位置不一致字母一致，考虑用哈希解决，但初步设想用
char值和来确定- 最后参考官方解解决，排序再比较
package sj.shimmer.algorithm.ten_3;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Created by SJ on 2021/2/22.
*/
class D29 {
public static void main(String[] args) {
// System.out.println(groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
System.out.println(groupAnagrams(new String[]{"","b"}));
System.out.println(groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"}));
}
public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
image
官方解
-
排序
如上；转换为char数组，排序，做key进行存放
- 时间复杂度：O(nklogk)
- 空间复杂度：O(nk)
-
计数
用每个字母出现的个数来做标志进行存储，算是变相排序了吧
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<String, List<String>>(); for (String str : strs) { int[] counts = new int[26]; int length = str.length(); for (int i = 0; i < length; i++) { counts[str.charAt(i) - 'a']++; } // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键 StringBuffer sb = new StringBuffer(); for (int i = 0; i < 26; i++) { if (counts[i] != 0) { sb.append((char) ('a' + i)); sb.append(counts[i]); } } String key = sb.toString(); List<String> list = map.getOrDefault(key, new ArrayList<String>()); list.add(str); map.put(key, list); } return new ArrayList<List<String>>(map.values()); } }
