数据结构与算法打卡-Day13

字母异位词分组

原题链接: 49. 字母异位词分组

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 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] 仅包含小写字母

题解：

 // 字母异位词分组
 // 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 // 示例:
 // 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
 // 输出:
 // [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
 // 说明：
 // 所有输入均为小写字母。
 // 不考虑答案输出的顺序。
 // 解法一：哈希表
 public List<List<String>> groupAnagrams(String[] strs) {
     // 初始化哈希表
     Map<String, List<String>> map = new HashMap<>();
     // 遍历字符串数组
     for (String str : strs) {
         // 将字符串转换为字符数组
         char[] array = str.toCharArray();
         // 对字符数组进行排序
         Arrays.sort(array);
         // 将字符数组转换为字符串
         String key = new String(array);
         // 如果哈希表中不包含key，则将key加入哈希表
         if (!map.containsKey(key)) {
             map.put(key, new ArrayList<>());
         }
         // 将字符串加入哈希表
         map.get(key).add(str);
     }
     // 返回哈希表的值
     return new ArrayList<>(map.values());
 }

思路：

这道题的主要思路是使用哈希表来解决字母异位词分组的问题。具体步骤如下：

1. 初始化一个哈希表，键是字符串，值是字符串列表。
2. 遍历给定的字符串数组。对于每一个字符串，执行以下操作：
   • 将字符串转换为字符数组。
   • 对字符数组进行排序。这样，所有的字母异位词在排序后都会得到相同的结果。
   • 将排序后的字符数组转换回字符串，作为哈希表的键。
3. 检查哈希表中是否已经存在这个键：
   • 如果不存在，那么在哈希表中添加这个键，并将其对应的值初始化为一个空的列表。
   • 如果存在，那么直接跳过这一步。
4. 将当前的字符串添加到哈希表中这个键对应的列表中。
5. 遍历完所有的字符串后，哈希表中的每一个键值对都对应了一组字母异位词。将哈希表的所有值转换为列表并返回，这就是最终的结果。

这种方法的时间复杂度是O(NMlogM)，其中N是字符串数组的长度，M是字符串的最大长度。空间复杂度是O(NM)，用于存储哈希表。