LeetCode 49. 字母异位词分组 Java 实现

在面试和算法练习中，字母异位词分组是一道高频出现的中等难度题目。核心挑战在于如何高效判断两个字符串是否互为变位（Anagram），并将它们归类。

题目描述

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

示例 1:

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

解释：

• 没有字符串可以通过重新排列形成 "bat"。
• "nat" 和 "tan" 是字母异位词。
• "ate"、"eat" 和 "tea" 是字母异位词。

示例 2:

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

提示：

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

核心思路

什么是字母异位词？简单来说，就是字母组成相同但顺序不同的单词。比如 "eat"、"tea"、"ate" 都由 a, e, t 组成。

解题的关键在于找到一个唯一的特征来标识一组异位词。最直观的方法是：将单词的字母排序。只要两个单词是异位词，排序后的结果一定完全相同。

例如：

• "eat" → 排序后 → "aet"
• "tea" → 排序后 → "aet"
• "ate" → 排序后 → "aet"

这个排序后的字符串就像指纹一样，我们可以利用哈希表（HashMap）将具有相同特征的单词聚合在一起。

代码实现

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 使用 HashMap 存储分组，Key 为排序后的特征字符串，Value 为原单词列表
        Map<String, List<String>> map = new HashMap<>();

        for (String word : strs) {
            // 将字符串转为字符数组并排序，生成特征键
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String key =  (chars);

            
             (!map.containsKey(key)) {
                map.put(key,  <>());
            }
            map.get(key).add(word);
        }

        
          <>(map.values());
    }
}