【LC100】No49. 字母异位词分组

题目描述

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

提示：

• 1 <= strs.length <= 104

• 0 <= strs[i].length <= 100

• strs[i] 仅包含小写字母

示例

示例 1：

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2：

输入: strs = [""]
输出: [[""]]

示例 3：

输入: strs = ["a"]
输出: [["a"]]

链接

思路

本题核心思路：如何判断几个单词使用的字母是否相同——

当字母数量相同时，对每个单词进行排序，排序后单词相同，则可以判断原单词是字母异位词。

看到按任意顺序和分组，可以想到按照字母排序后的单词做哈希表映射。

解法一：普通排序加分组

使用 map 存储处理后的结果，key 为排序后的单词，value 为字符串 list，保存排序前的单词。

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            // 对每个单词按字母排序
            char[] s = strs[i].toCharArray();
            Arrays.sort(s);
            // 按照排序后的单词放入map中
            List<String> list = map.getOrDefault(new String(s), new ArrayList<>());
            list.add(strs[i]);
            map.put(new String(s), list);
        }
        // 返回map的value集合
        return new ArrayList<>(map.values());
    }
}

• 时间复杂度：O(n * klogk)：n为strs的数组长度，klogk为排序的时间复杂度

• 空间复杂度：O(n * k)：二元map占用的空间

解法二：Java8的Stream的方法

看到分组，可以想到 stream 的 groupingBy 方法。

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs).collect(
            Collectors.groupingBy(str -> {
                char[] chars = str.toCharArray();
                Arrays.sort(chars);
                return new String(chars); 
            })
        ).values());
    }
}

• 时间复杂度：O(n * klogk)：groupingBy 的时间复杂度是 O(n)，排序的时间复杂度是klogk

• 空间复杂度：O(n * k)：groupingBy 产生的 map 和方法一中一致