Group Anagrams: Write a method to sort an array of strings so that all the anagrams are next to each other.
Hints: #177, #182, #263, #342
解法1
Anagram是字谜的意思，其实并不懂这个Anagram是啥东西的话没有办法做这道题。
如果说一个word是由另一个word的字母重排列组成，那么它们两个互为Anagram。比如LISTEN和SLIENT就是Anagram。
那么也就是说互为Anagram的两个字符串有下面特性：
- 长度相同
- 每个字母的数量相同
- 如果把字符串内的字母排序，那么它们的结果相同
代码：
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
|
class Word implements Comparable {
String origin;
String sorted;
int compareTo(Word another) {
return this.sorted.compareTo(another.sorted);
}
}
public List<String> groupAnagrams(List<String> strings) {
List<Word> words = new ArrayList<>();
for (String string : strings) {
words.add(makeWord(string));
}
Collections.sort(words);
List<String> result = new ArrayList<>();
for (Word word : words) {
result.add(word.getOrigin());
}
return result;
}
private Word makeWord(String string) {
char[] chars = string.charArray();
Arrays.sort(chars);
return new Word(string, new String(chars));
}
|
时间复杂度：O(s * log s * a + a * log a + a)，s是平均字符串长度，a是数组长度。
解法2
解法1对每个字符串做了排序，然后又对整个数组进行了排序。说起来题目只要求互为Anagram的字符串分组，没有要求排序，那么可以用Map对其进行分组，然后再合并一下返回。
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
|
public List<String> groupAnagrams(List<String> strings) {
Map<String, List<String>> letterCountMap = new HashMap<>();
for (String string : strings) {
String letterCount = countLetter(string);
List<String> subResult = letterCountMap.get(letterCount);
if (subResult == null) {
subResult = new ArrayList<>();
letterCountMap.put(letterCount, subResult);
}
subResult.add(string);
}
List<String> result = new ArrayList<>();
for (List<String> subResult : letterCountMap.values()) {
result.addAll(subResult);
}
return result;
}
private String countLetter(String string) {
int[] count = new int[26]; // 假设26个英文字母，而且都是小写
for (int i = 0; i < string.length(); i++) {
count[string.charAt(i) - 'a']++;
}
String result = "";
for (int i = 0; i < count.length; i++) {
if (count[i] == 0) {
continue;
}
result += "" + ('a' + i) + count[i];
}
return result;
}
|
时间复杂度：O(s * a + a)，s是平均字符串的长度，a是数组长度。
评论