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

【Leetcode hot 100】49.字母异位词分组

web 2025/8/5 15:49:32

题目链接

49.字母异位词分组

题目描述

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

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
解释：

在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [“”]
输出: [[“”]]

示例 3:

输入: strs = [“a”]

输出: [[“a”]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

问题解答

方法一：排序法（推荐）

核心思想
字母异位词的字符组成完全相同，仅顺序不同。因此，对每个字符串的字符进行排序后，字母异位词会得到相同的排序结果。以排序后的字符串作为哈希表的键，即可将所有字母异位词分到同一组。

实现步骤

创建一个HashMap，键为排序后的字符串（作为字母异位词的唯一标识），值为存储该组字母异位词的List。
遍历输入的字符串数组，对每个字符串：
- 转换为字符数组并排序。
- 将排序后的字符数组转回字符串，作为哈希表的键。
- 若键已存在，将当前字符串加入对应List；若不存在，新建List并添加当前字符串，再存入哈希表。
最后，将哈希表中所有List收集为结果返回。

代码实现

import java.util.*;class Solution {public List<List<String>> groupAnagrams(String[] strs) {if (strs == null || strs.length == 0) {return new ArrayList<>();}// 哈希表：键为排序后的字符串，值为字母异位词列表Map<String, List<String>> map = new HashMap<>();for (String s : strs) {// 将字符串转换为字符数组并排序char[] chars = s.toCharArray();Arrays.sort(chars);String key = new String(chars); // 排序后的字符串作为键// 若键不存在则新建列表，否则直接添加if (!map.containsKey(key)) {map.put(key, new ArrayList<>());}map.get(key).add(s);}// 返回所有分组结果return new ArrayList<>(map.values());}
}

方法二：计数法

核心思想
统计每个字符串中每个字符（a-z）的出现次数，用这个计数结果作为唯一标识（例如“aab”的计数为[2,1,0,...0]）。相同计数结果的字符串即为字母异位词。

实现步骤

创建一个HashMap，键为字符计数的字符串表示（如“2,1,0,…”），值为存储该组字母异位词的List。
遍历输入的字符串数组，对每个字符串：
- 用长度为26的数组统计每个字符（a-z）的出现次数。
- 将计数数组转换为字符串（如用逗号分隔每个数字）作为键。
- 若键已存在，将当前字符串加入对应List；若不存在，新建List并添加当前字符串，再存入哈希表。
最后，将哈希表中所有List收集为结果返回。

代码实现

import java.util.*;class Solution {public List<List<String>> groupAnagrams(String[] strs) {if (strs == null || strs.length == 0) {return new ArrayList<>();}// 哈希表：键为字符计数的字符串表示，值为字母异位词列表Map<String, List<String>> map = new HashMap<>();int[] count = new int[26]; // 统计每个字符的出现次数（a-z）for (String s : strs) {Arrays.fill(count, 0); // 重置计数数组// 统计当前字符串中每个字符的次数for (char c : s.toCharArray()) {count[c - 'a']++;}// 将计数数组转换为字符串作为键（用逗号分隔避免歧义）StringBuilder sb = new StringBuilder();for (int i = 0; i < 26; i++) {sb.append(count[i]).append(',');}String key = sb.toString();// 若键不存在则新建列表，否则直接添加if (!map.containsKey(key)) {map.put(key, new ArrayList<>());}map.get(key).add(s);}// 返回所有分组结果return new ArrayList<>(map.values());}
}