字母异位词分组 | LeetCode-49 | 哈希集合

在字符

---

LeetCode链接：242. 有效的字母异位词

---

1.题目描述

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• $1 <= strs.length <= 10^4$
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

2.题解

2.1 排序

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建一个哈希表用于存储异位词分组
        Map<String, List<String>> map = new HashMap<>();
        
        // 遍历输入字符串数组
        for (String str : strs) {
            // 将字符串转换为字符数组
            char[] chs = str.toCharArray();
            // 对字符数组进行排序，得到异位词的统一表示
            Arrays.sort(chs);
            // 将排序后的字符数组转换为字符串作为键
            String key = new String(chs);
            // 获取当前键对应的列表，如果不存在则创建一个新的列表
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            // 将当前字符串加入对应的列表中
            list.add(str);
            // 更新哈希表
            map.put(key, list);
        }

        // 返回所有异位词分组，作为列表列表形式
        return new ArrayList<List<String>>(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());
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // str -> intstream -> sort -> collect by StringBuilder
        return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> str.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString())).values());
    }
}

2.2 计数

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建一个哈希表，用于存储异位词分组
        Map<String, List<String>> map = new HashMap<>();

        // 遍历输入字符串数组
        for (String str : strs) {
            // 创建一个长度为26的数组，记录每个字母在字符串中的出现次数
            int[] counts = new int[26];
            for (int i = 0; i < str.length(); i++) {
                counts[str.charAt(i) - 'a']++;
            }

            // 使用StringBuilder构造唯一的键，基于字符及其频率
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < counts.length; i++) {
                if (counts[i] != 0) {
                    // 将字符及其出现次数加入到键中
                    sb.append((char) ('a' + i)).append(counts[i]);
                }
            }
            String key = sb.toString();

            // 获取当前键对应的列表，如果不存在则创建一个新的列表
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            // 将当前字符串加入对应的列表中
            list.add(str);
            // 更新哈希表
            map.put(key, list);
        }

        // 返回所有异位词分组，以列表列表的形式
        return new ArrayList<List<String>>(map.values());
    }
}