题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例 1：

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

  • 所有输入均为小写字母。

  • 不考虑答案输出的顺序。

思路

方法一：排序
字母相同，但排列不同的字符串，排序后都一定是相同的。因为每种字母的个数都是相同的，那么排序后的字符串就一定是相同的。

这里可以利用 stream 的 groupingBy 算子实现直接返回结果：

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

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs)
            .collect(Collectors.groupingBy(str -> {
                // 返回 str 排序后的结果。
                // 按排序后的结果来grouping by，算子类似于 sql 里的 group by。
                char[] array = str.toCharArray();
                Arrays.sort(array);
                return new String(array);
            })).values());
    }
}

思路

方法二：统计每个字母的个数
题目中说了所有输入均为小写字母，所以还可以只用一个数组，统计字符串中每个字符的个数，最终会生成一个新的字符串，如果生成新的字符串相同，说明他们是字母异位词，画个图看一下


可以看到，只要是字母异位词，通过上面的方式转换，他们生成的字符串都是一样的。

public List<List<String>> groupAnagrams(String[] strs) {
    //边界条件判断
    if (strs == null || strs.length == 0)
        return new ArrayList<>();
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] ca = new char[26];
        //统计字符串中每个字符串出现的次数
        for (char c : s.toCharArray())
            ca[c - 'a']++;
        //统计每个字符出现次数的数组转化为字符串
        String keyStr = String.valueOf(ca);
        if (!map.containsKey(keyStr))
            map.put(keyStr, new ArrayList<>());
        map.get(keyStr).add(s);
    }
    return new ArrayList<>(map.values());
}

时间复杂度：O(n)。

空间复杂度：O(n)。

作者：LeetCode-Solution
来源：力扣（LeetCode）

本公众号分享自己从程序员小白到经历春招秋招斩获10几个offer的面试笔试经验，其中包括【Java】、【操作系统】、【计算机网络】、【设计模式】、【数据结构与算法】、【大厂面经】、【数据库】期待你加入！！！

1.计算机网络----三次握手四次挥手
2.梦想成真-----项目自我介绍
3.你们要的设计模式来了
4.一字一句教你面试“个人简介”
5.接近30场面试分享
6.你们要的免费书来了