LeetCode 49. 字母异位词分组：巧用哈希表与排序算法

在日常的业务开发和算法刷题中，字符串处理是一个非常经典的命题。今天和大家分享一道 LeetCode 的中等难度高频题——字母异位词分组。这道题完美契合了“找规律 + 巧用数据结构”的解题思路。

📝 题目描述

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

注意：字母异位词是由重新排列源单词的所有字母得到的一个新单词（即组成单词的字母和数量完全相同，只是顺序不同）。

示例：

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

解释:

• 在 strs 中没有字符串可以通过重新排列来形成 "bat"。

• 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。

• 字符串 "ate"、"eat" 和 "tea" 是字母异位词。

💡 解题思路：寻找唯一标识 (Key)

这道题的核心痛点是：如何判断两个字符串是“兄弟”（字母异位词）？

由于字母异位词的字符组成完全相同，我们如果把每一个字符串里的字符按照字母顺序重新打散并排序，那么所有的“字母异位词”都会变成同一个固定的字符串。

例如：

• "eat" 排序后变成 "aet"

• "tea" 排序后变成 "aet"

• "ate" 排序后变成 "aet"

因此，这个排序后的字符串 "aet" 就可以作为 HashMap 中的 唯一键 (Key)。而哈希表的值 (Value) 则是一个 List<String>，用来存放所有属于这个 Key 的原始字符串。

💻 代码实现

这是我最初的实现思路，老老实实判断哈希表中是否已经存在这个 Key，如果不存在就 new 一个 ArrayList 存进去：

import java.util.*;

public class GroupAnagrams {
    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        
        // 先将字母异位词通过排序后的字符串作为 key
        Map<String, List<String>> map = new HashMap<>();
        
        // 对原来数组中的每个元素进行字母排序形成唯一的 key
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            
            // 判断当前 key 是否已存在
            if (map.get(key) == null) {
                List<String> list = new ArrayList<>();
                // 将当前元素加入 list
                list.add(str);
                map.put(key, list);
            } else {
                map.get(key).add(str);
            }
        }
        
        // 打印结果
        System.out.println(new ArrayList<>(map.values()));
    }
}

📊 复杂度分析

• 时间复杂度：O(N * K log K），其中 N 是字符串数组 strs 的长度，K 是数组中字符串的最大长度。我们需要遍历 N个字符串，而每个字符串的字符排序需要花费 O(K log K)的时间。

• 空间复杂度：O(N*K)。主要为 HashMap 存储所有字符串所需的额外空间。

📌 总结归纳

这道题是 “设计键值映射” 思想的典型应用。在业务开发中，当我们需要对一堆看似散乱的数据进行分组聚合时，寻找共性、设计一个能唯一标识这一组数据的特征值（Key），往往是破局的关键所在。