Java字母异位词分组leetcode_49

49、字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

解法一：

​ 将所有字符串根据字母排序，因为每种字母的个数都是相同的，那么排序后的字符串就一定是相同的。

​ groupingBy 算子计算完以后，返回的是一个 Map，map 的键是每种排序后的字符串，值是聚合的原始字符串，我们只关心值，所以我们最后 new ArrayList<>(map.values())。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs)
            .collect(Collectors.groupingBy(str -> {
                char[] chs = str.toCharArray();
                Arrays.sort(chs);
                return new String(chs);
            })).values());
    }
}
1
2
3
4
5
6
7
8
9
10

执行用时：9 ms, 在所有 Java 提交中击败了30.84%的用户

内存消耗：44.1 MB, 在所有 Java 提交中击败了93.63%的用户

通过测试用例：117 / 117

解法二：

​ 编码计数，对每个字符串计数得到该字符串的计数数组，对于计数数组相同的字符串，就互为异位词。
​ 因为数组类型没有重写 hashcode() 和 equals() 方法，因此不能直接作为 HashMap 的 Key 进行聚合，那么我们就 把这个数组手动编码变成字符串就行了。
​ 比如将 [b,a,a,a,b,c] 编码成 a3b2c1，使用编码后的字符串作为 HashMap 的 Key 进行聚合。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Stream.of(strs)
            .collect(Collectors.groupingBy(str -> {
                int[] count = new int[26];
                for(int i = 0;i < str.length();i++){
                    count[str.charAt(i) - 'a']++;
                }
                StringBuilder sb = new StringBuilder();
                for(int i = 0;i < 26;i++){
                    if(count[i] != 0){
                        sb.append('a' + i);
                        sb.append(count[i]);
                    }
                }
                return sb.toString();
            })).values());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

执行用时：15 ms, 在所有 Java 提交中击败了13.48%的用户

内存消耗：44.5 MB, 在所有 Java 提交中击败了56.42%的用户

通过测试用例：117 / 117