目录

问题描述

示例

示例 1

示例 2

示例 3

约束条件

解决方案

思路

算法步骤

过题图片

代码实现

复杂度分析

题目链接

结论

---

问题描述

给定一个字符串数组，需要将其中的字母异位词分组。字母异位词是指通过重新排列源单词的所有字母得到的新单词。要求可以按任意顺序返回结果列表。

示例

示例 1

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

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

示例 2

输入: strs = [""]

输出: [[""]]

示例 3

输入: strs = ["a"]

输出: [["a"]]

约束条件

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

解决方案

思路

解决这个问题的关键在于识别哪些字符串是字母异位词。由于字母异位词的字母种类和数量完全相同，我们可以通过对字符串中的字母进行排序，然后比较排序后的字符串是否相同来判断两个字符串是否为字母异位词。

算法步骤

1. 创建一个空的Map，用于存储排序后的字符串和对应的原始字符串列表。
2. 遍历输入的字符串数组strs。
3. 对于每个字符串，将其转换为字符数组，并进行排序。
4. 将排序后的字符数组转换回字符串。
5. 检查Map中是否已经存在这个排序后的字符串作为键，如果存在，则将原始字符串添加到对应的列表中；如果不存在，则创建一个新的列表，并将原始字符串添加进去。
6. 将这个列表与排序后的字符串作为键一起存入Map。
7. 最后，将Map中的所有值（即所有分组好的列表）放入一个新的列表中，并返回。

过题图片

代码实现

java

import java.util.*;class Solution {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 sortedStr = new String(array); // 获取排序后的字符串List<String> tempList = map.getOrDefault(sortedStr, new ArrayList<>());tempList.add(str); // 将排序后相等的字符串存入一个集合map.put(sortedStr, tempList); // 将该字符串存入以 “sortedStr”为key，list为value的map键值对中}return new ArrayList<>(map.values()); // 返回所有分组好的列表}
}

复杂度分析

• 时间复杂度：O(n * k * log(k))，其中n是字符串数组的长度，k是字符串的最大长度。这是因为我们需要对每个字符串进行排序，而排序的时间复杂度是O(k * log(k))。
• 空间复杂度：O(n * k)，因为我们需要存储所有字符串的排序版本和原始字符串。

题目链接

49. 字母异位词分组 - 力扣（LeetCode）

结论

通过将每个字符串的字母排序，我们可以有效地识别并分组字母异位词。字符串的排序是基于字符的Unicode值进行的，这意味着字符串会按照从第一个字符开始的字典顺序进行排序。如果第一个字符相同，则比较第二个字符，依此类推。