当前位置：首页 > news >正文

LeetCode经典题解：49、字母异位词分组

news 2025/7/21 0:39:54

LeetCode经典题解：字母异位词分组

“字母异位词分组”是哈希表应用的经典题目，解法思路清晰但细节易混。本文用“场景化记忆法”帮你吃透解法，从代码逻辑到记忆技巧一网打尽。

一、题目描述

题目：给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的所有字母得到的新单词（例如，“eat”和“tea”是字母异位词）。

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

二、最优解法：哈希表 + 特征归一

方法一：排序法（直观高效）

代码实现

import java.util.*;class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 哈希表：key是"特征值"（排序后的字符串），value是同组异位词列表Map<String, List<String>> map = new HashMap<>();for (String s : strs) {// 将字符串转换为字符数组，排序后作为"特征值"char[] chars = s.toCharArray();Arrays.sort(chars);String key = new String(chars);// 若key不存在则创建新列表，否则直接添加到对应列表map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);}// 哈希表的值就是分组结果return new ArrayList<>(map.values());}
}

解法解析

核心逻辑：字母异位词排序后得到的字符串完全相同（例如“eat”和“tea”排序后都是“aet”），用排序后的字符串作为“特征值”，通过哈希表分组。
时间复杂度：O(n * k log k)（n 是字符串数量，k 是最长字符串长度，排序耗时 k log k）。
空间复杂度：O(n * k)（哈希表存储所有字符串）。

方法二：字符频率法（适合长字符串）

代码实现

import java.util.*;class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String s : strs) {// 统计26个小写字母的出现次数int[] count = new int[26];for (char c : s.toCharArray()) {count[c - 'a']++;}// 将频率数组转为字符串作为key（例如"1,0,2,..."）StringBuilder key = new StringBuilder();for (int num : count) {key.append(num).append(','); // 加逗号避免歧义（如11和1,1）}map.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);}return new ArrayList<>(map.values());}
}

解法解析

核心逻辑：字母异位词的字符频率完全相同（例如“eat”和“tea”的 e:1, a:1, t:1），用频率数组的字符串形式作为“特征值”分组。
优势：避免排序耗时，适合字符串长（k 大）但字符集小（如仅小写字母）的场景。

三、为什么这样解？—— 异位词的“共性”与分组逻辑

1. 异位词的本质

字母异位词的核心共性是“字符种类和数量完全相同，顺序不同”。因此，只要找到一种“归一化”方法（如排序、统计频率），就能将异位词映射到同一“特征值”。

2. 哈希表的作用

哈希表的“键值对”结构天然适合“分组”：

键（key）：异位词的“特征值”（排序后的字符串或频率字符串），确保同一组异位词映射到同一键。
值（value）：存储同一组的所有异位词，最终直接返回所有值的集合。

四、高效记忆技巧：把逻辑变成“整理文件”的场景

用生活化场景理解代码，记住“角色+动作”即可还原解法：

1. 角色赋值

哈希表（map）：扮演“文件柜”，每个抽屉（key）对应一组异位词。
排序/频率统计：扮演“标签机”，给每个字符串打“特征标签”（确保异位词标签相同）。
字符串数组（strs）：扮演“一堆待整理的文件”，需要按标签分类放进文件柜。

2. 场景故事：整理文件的流程

（以排序法为例）
你是档案管理员，要把一堆文件（strs）按“内容相同、顺序不同”分类：
① 拿起一份文件（字符串），用“标签机”（排序）给它打标签（排序后的字符串，如“tea”→“aet”）；
② 查看文件柜（map）里有没有这个标签的抽屉：

有则直接把文件放进去；
没有则新建抽屉（key），再放文件；
③ 所有文件处理完后，文件柜里的抽屉就是分组结果。

3. 两种方法的记忆点

方法	标签机（特征值）	适用场景	一句话总结
排序法	排序后的字符串	字符串短、字符集大	“排序归一，哈希分组”
频率统计法	字符频率拼接的字符串	字符串长、字符集小（如26字母）	“统计频率做标签，哈希来归类”