49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
先将字母排序，然后映射到字典map中
image.png
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> list = new ArrayList<>();
HashMap<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] arr = str.toCharArray();
//排序
Arrays.sort(arr);
String key = String.valueOf(arr);
//字典归类
if (map.containsKey(key)) {
map.get(key).add(str);
} else {
List<String> sublist=new ArrayList<>();
sublist.add(str);
map.put(key, sublist);
}
}
return new ArrayList<List<String>>(map.values());
}
时间复杂度：排序的话算作 O（K log（K））,最外层的 for 循环，所以就是 O（n K log（K））。
空间复杂度：O（NK），用来存储结果。
方案二：
算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。
利用这个，我们把每个字符串都映射到一个正数上。
用一个数组存储质数 prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103}。
然后每个字符串的字符减去 ' a ' ，然后取到 prime 中对应的质数。把它们累乘。
例如 abc ，就对应 'a' - 'a'， 'b' - 'a'， 'c' - 'a'，即 0, 1, 2，也就是对应素数 2 3 5，然后相乘 2 *3 *5 = 30，就把 "abc" 映射到了 30。
image.png
public List<List<String>> groupAnagrams(String[] strs) {
//每个字母对应一个质数
//每个字母对应一个质数
int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199};
List<List<String>> list = new ArrayList<>();
HashMap<Integer, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] arr = str.toCharArray();
int key = 1;
for (char s : arr) {
//防止 a-'a'=0 导致 所有改为 s-'a'+1 a,aa是同一个的bug 的不过
key *= prime[s - 'a'+1];
}
//字典归类
if (map.containsKey(key)) {
map.get(key).add(str);
} else {
List<String> sublist = new ArrayList<>();
sublist.add(str);
map.put(key, sublist);
}
}
return new ArrayList<List<String>>(map.values());
}
image.png
时间复杂度：O（n * K），K 是字符串的最长长度。
空间复杂度：O（NK），用来存储结果。
这个解法时间复杂度，较解法二有提升，但是有一定的局限性，因为求 key 的时候用的是累乘，可能会造成溢出，超出 int 所能表示的数字。
方案三：
参考这里，记录字符串的每个字符出现的次数从而完成映射。因为有 26 个字母，不好解释，我们假设只有 5 个字母，来看一下怎么完成映射。
首先初始化 key = "0#0#0#0#0#"，数字分别代表 abcde 出现的次数，# 用来分割。
这样的话，"abb" 就映射到了 "1#2#0#0#0"。
"cdc" 就映射到了 "0#0#2#1#0"。
"dcc" 就映射到了 "0#0#2#1#0"。
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
int[] freq = new int[26];
StringBuilder stringBuilder = new StringBuilder(100);
//记录每个字符的次数
for (int i = 0; i < str.length(); i++) {
freq[str.charAt(i) - 'a'] ++;
}
for (int i = 0; i < freq.length; i++) {
stringBuilder.append("#" + freq[i]);
}
String key = stringBuilder.toString();
if (map.containsKey(key)) {
map.get(key).add(str);
continue;
}
List<String> list = new ArrayList<>();
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
时间复杂度： O（nK）。
空间复杂度：O（NK），用来存储结果。
