力扣经典150题第四十二题：字母异位词分组
引言
本篇博客介绍了力扣经典150题中的第四十二题：字母异位词分组。题目要求将给定的字符串数组中的字母异位词分组，并返回分组结果。
题目详解
给定一个字符串数组 strs，将其中字母异位词（由重新排列源单词的所有字母得到的新单词）组合在一起，最终返回分组后的结果列表。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
解题思路
要将字母异位词分组，可以使用哈希表进行处理：
- 创建一个哈希表 map，键为字符串的字符排序后的字符串（作为异位词的标识），值为该异位词所在的分组列表。
- 遍历字符串数组strs，对于每个字符串s：
- 将 s 转换成字符数组，并进行排序得到新的字符串 sortedStr，作为哈希表的键。
- 如果 sortedStr 在哈希表中不存在，创建一个新的分组列表，并将当前字符串 s 加入到列表中，同时在哈希表中添加 sortedStr 到对应的分组列表。
- 如果 sortedStr 在哈希表中存在，直接将当前字符串 s 加入到对应的分组列表中。
- 最终，遍历哈希表的所有值，将分组列表组成的结果返回。
通过上述步骤，可以将字母异位词分组并返回结果列表。
代码实现
import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; public class GroupAnagrams { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { // 将字符串转换成字符数组并排序 char[] charArray = s.toCharArray(); Arrays.sort(charArray); String sortedStr = new String(charArray); // 如果 sortedStr 不在 map 中，创建一个新的分组列表 if (!map.containsKey(sortedStr)) { map.put(sortedStr, new ArrayList<>()); } // 将当前字符串加入到对应的分组列表中 map.get(sortedStr).add(s); } // 返回哈希表中的所有分组列表 return new ArrayList<>(map.values()); } public static void main(String[] args) { GroupAnagrams solution = new GroupAnagrams(); // 示例测试 String[] strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"}; System.out.println("输入: " + Arrays.toString(strs1)); System.out.println("输出: " + solution.groupAnagrams(strs1)); String[] strs2 = {""}; System.out.println("输入: " + Arrays.toString(strs2)); System.out.println("输出: " + solution.groupAnagrams(strs2)); String[] strs3 = {"a"}; System.out.println("输入: " + Arrays.toString(strs3)); System.out.println("输出: " + solution.groupAnagrams(strs3)); } }
示例演示
展示了几个不同的示例测试，验证了字母异位词分组的功能。
复杂度分析
该解法的时间复杂度为 O(n * k log k)，其中 n 是字符串数组 strs 的长度，k 是字符串的最大长度。空间复杂度为 O(n * k)，主要是哈希表 map 存储的空间。
