如何利用集合高效地对变位词（Anagrams）进行分组？

嘿，这个变位词分组的问题我之前做项目时刚好碰到过！用Java的集合框架来处理简直是量身定做，尤其是HashMap，我给你分享两个高效的实现思路，保证好用～

核心思路铺垫 #

变位词的本质是：字符组成完全相同，只是顺序不同。所以我们只需要找到一个能唯一代表这类单词的“标识”，把具有相同标识的单词归为一组就行。而HashMap正好可以帮我们把“标识”作为key，对应的单词列表作为value，完美适配这个需求。

方法一：排序字符生成标识（通用场景首选） #

这是最直观也最通用的方法，不管单词里是什么字符（只要能排序）都能用：

1. 遍历输入的每个单词，把它转成字符数组后排序，再转回字符串——这个排序后的字符串就是该变位词组的唯一标识。
2. 用HashMap存储，key是排序后的字符串，value是对应的变位词列表。如果key不存在，就新建一个空列表；如果存在，就把当前单词加到列表里。
3. 最后把HashMap里的所有value取出来，就是分组好的结果。

给你贴个可直接跑的代码：

import java.util.*;

public class AnagramGrouper {
    public static List<List<String>> groupAnagrams(String[] strs) {
        // 处理空输入的边界情况
        if (strs == null || strs.length == 0) return new ArrayList<>();
        
        Map<String, List<String>> anagramMap = new HashMap<>();
        for (String s : strs) {
            // 生成排序后的key
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            
            // 简洁的写法：如果key不存在就初始化列表，然后添加当前单词
            anagramMap.computeIfAbsent(key, k -> new ArrayList<>());
            anagramMap.get(key).add(s);
        }
        
        // 把map的所有值转成最终的List集合
        return new ArrayList<>(anagramMap.values());
    }

    public static void main(String[] args) {
        String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result = groupAnagrams(input);
        System.out.println(result);
        // 输出示例：[[eat, tea, ate], [tan, nat], [bat]]（分组正确即可，顺序可能因HashMap特性略有不同）
    }
}

这个方法的时间复杂度是O(nk log k)，其中n是单词总数，k是单个单词的最长长度。排序的开销是主要部分，对于大多数场景来说完全够用。

方法二：字符计数生成标识（长单词优化版） #

如果你的输入里有很多长单词，排序的开销就有点大了。这时候可以用字符计数的方式生成标识，把时间复杂度降到O(nk)：

1. 假设单词都是小写英文字母（如果是其他字符集可以调整数组长度），用一个长度为26的数组统计每个字母出现的次数。
2. 把这个计数数组转成一个唯一的字符串作为key（比如用#分隔每个数字，避免11和1+1这种歧义情况）。
3. 后续逻辑和方法一一样，用HashMap分组。

代码示例：

import java.util.*;

public class AnagramGrouperOptimized {
    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        
        Map<String, List<String>> anagramMap = new HashMap<>();
        int[] charCount = new int[26]; // 对应a-z的出现次数
        
        for (String s : strs) {
            Arrays.fill(charCount, 0); // 每次循环重置计数数组
            // 统计每个字符的出现次数
            for (char c : s.toCharArray()) {
                charCount[c - 'a']++;
            }
            
            // 把计数数组转成唯一的key
            StringBuilder keyBuilder = new StringBuilder();
            for (int count : charCount) {
                keyBuilder.append('#').append(count);
            }
            String key = keyBuilder.toString();
            
            // 添加当前单词到对应分组
            anagramMap.computeIfAbsent(key, k -> new ArrayList<>());
            anagramMap.get(key).add(s);
        }
        
        return new ArrayList<>(anagramMap.values());
    }

    public static void main(String[] args) {
        String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result = groupAnagrams(input);
        System.out.println(result);
    }
}

这个方法对于长单词来说效率提升很明显，因为统计字符是线性时间，比排序的对数时间快多了。

一些小提醒 #

• 空字符串处理：两种方法都能自动把所有空字符串分到同一组，因为排序后还是空，计数数组全0。
• 大小写问题：如果题目不区分大小写，记得先把单词转成小写（或大写）再处理，比如s = s.toLowerCase()。
• 性能细节：Java 8+的computeIfAbsent方法比先判断containsKey再put要简洁，而且内部实现更高效。

备注：内容来源于stack exchange，提问作者Pabitra