为字母异位词设置分配哈希值相同的数据结构
给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词指字母相同，但排列不同的字符串。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
思路：
观察可以发现，我们需要提取字母异位词之间满足一定的「等价性」，我们需要提取出能够表达这个等价性的某一个等价特征，作为放在哈希表中作为 key，而 value 指向一个结果列表，才能依次归类这些字符串。
我们可以提取出一种方便处理的等价特征，比如将字母异位词按字典序排序以后得到的字符串，一定相同，我们可以以这个字符串作为 key 来执行哈希查找，快速定位到应该存放的结果集当中。排序方法多种多样，比如可以将字符串转化为字符数组，然后对字符数组执行排序。
当然，设字符串长度为 m，总字符串个数为 n，考虑排序的复杂度此方法的整体复杂度为 O(nmlogm)。我们使用了 O(mlogm) 的排序算法来寻找等价特征，考虑能否进一步降低其复杂度。
我们发现，还能用另一种方法描述这个等价特征，字母异位词的某一个单词中对应字母个数一定相同，我们可以以一个长度 26 的整型数组来描述这个特征，字母对应下标的数组数字即为该字母的出现次数。为了方便使用哈希表，我们构造一个类 Count 封装这个数组，重写其 equals 和 hashcode 方法（hashcode 实现方式不唯一，只要保证 equals 的元素 hashcode 结果一定相等即可，逆命题不必成立）。这样我们对每一个待选择的字符串，都构造一个 Count 作为哈希表的 key，放入对应的列表当中。由于我们遍历字符串计数字母的时间为 O(m) 复杂度，而哈希算法的复杂度为 O(|ε|)(|ε| 为字符集大小，这里是 26，为常数)，整体时间复杂度降至 O(nm)。
时间复杂度：O(nm)
空间复杂度：O(nm)
实现：
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
54
55
56
57
58
59
60
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> ret = new LinkedList<>();
Map<Count, List<String>> map = new HashMap<>();
for (String str : strs) {
Count cur = new Count(str);
if (map.containsKey(cur)) {
map.get(cur).add(str);
} else {
List<String> list = new LinkedList<>();
list.add(str);
ret.add(list);
map.put(cur, list);
}
}
return ret;
}
private class Count {
private int[] eigen = new int[26];
public int get(int index) {
return eigen[index];
}
public Count(String s) {
for (int i = s.length() - 1; i >= 0; i--) {
eigen[s.charAt(i) - 'a'] += 1;
}
}
@Override
public boolean equals(Object o) {
if (o == null) {
return false;
}
if (!(o instanceof Count)) {
return false;
}
for (int i = 0; i < 26; i++) {
if (eigen[i] != ((Count) o).get(i)) {
return false;
}
}
return true;
}
@Override
public int hashCode() {
int ret = 0;
for (int i = 0; i < 26; i++) {
ret *= 26;
ret += eigen[i];
}
return ret;
}
}
}
|
