来源Leetcode第49题字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
一开始做的时候，想着通过建一个哈希表来描述一个字符串有的字母，但是没做出来，还是要多看看JAVA的Hash啊
通用解法
对于每个字符串，比较它们的每个字符出现的个数是否相等，相等的话就把它们放在一个 list 中去，作为一个类别。最外层写一个 for 循环然后一一比较就可以，还可以用一个等大的布尔型数组来记录当前字符串是否已经加入的了 list 。比较两个字符串的字符出现的次数可以用一个 HashMap。
缺点就是，超时了
代码如下：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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> ans = new ArrayList<>();
//used 数组记录当前字符串是否已经加入list
boolean[] used = new boolean[strs.length];
//遍历string数组
for (int i = 0; i < strs.length; i++) {
List<String> temp = null;
if (!used[i]) {
temp = new ArrayList<String>();
temp.add(strs[i]);
//判断后续字符串是否字母出现次数一样
for (int j = i + 1; j < strs.length; j++) {
if (!used[j]&&equals(strs[i], strs[j])) {
used[j] = true;
temp.add(strs[j]);
}
}
}
if (temp != null) {
ans.add(temp);
}
}
return ans;
}
private boolean equals(String string1, String string2) {
Map<Character, Integer> hash = new HashMap<>();
//记录第一个字符串每个字符出现的次数，进行累加
for (int i = 0; i < string1.length(); i++) {
if (hash.containsKey(string1.charAt(i))) {
hash.put(string1.charAt(i), hash.get(string1.charAt(i)) + 1);
} else {
hash.put(string1.charAt(i), 1);
}
}
//记录第一个字符串每个字符出现的次数，将之前的每次减 1
for (int i = 0; i < string2.length(); i++) {
if (hash.containsKey(string2.charAt(i))) {
hash.put(string2.charAt(i), hash.get(string2.charAt(i)) - 1);
} else {
return false;
}
}
//判断每个字符的次数是不是 0 ，不是的话直接返回 false
Set<Character> set = hash.keySet();
for (char c : set) {
if (hash.get(c) != 0) {
return false;
}
}
return true;
}
来自题解
按计数分类
思路
当且仅当它们的字符计数（每个字符的出现次数）相同时，两个字符串是字母异位词。
算法
我们可以将每个字符串 s 转换为字符数 count，由26个非负整数组成，表示 a,b,c 的数量等。我们使用这些计数作为哈希映射的基础。
在 Java 中，我们的字符数 count 的散列化表示将是一个用 ＃ 字符分隔的字符串。例如，abbccc 将表示为 ＃1＃2＃3＃0＃0＃0 …＃0，其中总共有26个条目。 在 python 中，表示将是一个计数的元组。 例如，abbccc 将表示为 (1,2,3,0,0，…，0)，其中总共有 26 个条目。
代码如下：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
28class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
//初始化HASH Map
Map<String, List> ans = new HashMap<String, List>();
//count数组，标记出现的字母次数
int[] count = new int[26];
//foreach 遍历strs里的所有string
for (String s : strs) {
//count数组初始化为0
Arrays.fill(count, 0);
//统计字母出现次数
for (char c : s.toCharArray()) count[c - 'a']++;
//构造字符串
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < 26; i++) {
sb.append('#');
sb.append(count[i]);
}
String key = sb.toString();
//如果key(即统计字母次数字符串)没有出现在Map里，就添加key
if (!ans.containsKey(key)) ans.put(key, new ArrayList());
//往Map里增加key、s的映射
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
}
排序数组分类
思路
当且仅当它们的排序字符串相等时，两个字符串是字母异位词。
算法
维护一个映射 ans : {String -> List}，其中每个键 K 是一个排序字符串，每个值是初始输入的字符串列表，排序后等于 K。
在 Java 中，我们将键存储为字符串，例如，code。 在 Python 中，我们将键存储为散列化元组，例如，(‘c’, ‘o’, ‘d’, ‘e’)。
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map<String, List> ans = new HashMap<String, List>();
for (String s : strs) {
char[] ca = s.toCharArray();
Arrays.sort(ca);
String key = String.valueOf(ca);
if (!ans.containsKey(key)) ans.put(key, new ArrayList());
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
}
正整数的唯一分解定理
算术基本定理，又称为正整数的唯一分解定理，即：每个大于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。
1 | public List<List<String>> groupAnagrams(String[] strs) { |