LC 49.字母异位词分组

本文主要是介绍LC 49.字母异位词分组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

49.字母异位词分组

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

解法一(HashMap+排序)

思路分析：

1. 对于 满足 字符串中的字符 按字母顺序排序后的 字符串相同的 字符串为一组，因此我们可以使用哈希表来进行保存

2. 若对于一个字符串str，将其按照字母顺序重新排序后的字符串string，其在哈希表中出现过，则将str保存到哈希表中对应的列表中

3. 若没有出现过，则需要创建新的字符串列表，并进行保存

4. 遍历完字符串数组strs时，则完成了分组

实现代码如下：

class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 哈希表 统计字母异位词 出现的 字符串HashMap<String, List<String>> hashString = new HashMap<>();for (String str : strs) {    // 遍历数组strschar[] charArray = str.toCharArray();    // 将字符串转化为字符数组Arrays.sort(charArray);        // 对字符数组进行排序String string = Arrays.toString(charArray);    // 将排序好的字符数组转化为字符串List<String> stringList;    // 保存 相互为字母异位词的 字符串if (hashString.containsKey(string)) {    // 若哈希表中已存在该种字母异位词stringList = hashString.get(string);    // 则将保存列表返回} else {stringList = new ArrayList<>();        // 否则创建新列表}stringList.add(str);    // 将该字符串保存到对应的 字母异位词列表中hashString.put(string, stringList); // 并保存到哈希表}return new ArrayList<>(hashString.values());    // 将哈希表中的结果返回}
}

提交结果如下：

解答成功:执行耗时:9 ms,击败了30.66% 的Java用户内存消耗:46.4 MB,击败了8.04% 的Java用户

复杂度分析：

• 时间复杂度：$O(n\cdot (mlo{g}^m+2m))$，其中，m为每个字符串的长度，排序花费$O(mlo{g}^m)$，将其转化为字符数组和重新转化为字符串花费$O(2m)$，n指的是字符串数组strs的长度

• 空间复杂度：$O(n\cdot m)$

解法二(HashMap+计数)

思路分析：

1. 对于属于同一组字符异位词，除了按照规定顺序排序之后，可作为标识之外，还可以对其含有的字符进行计数，然后将其包含的字符和数目合并为一个标识字符串

2. 如此，即可作为map的关键值

实现代码如下：

class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 哈希表 统计字母异位词 出现的 字符串HashMap<String, List<String>> hashString = new HashMap<>();for (String str : strs) {    // 遍历数组strs// 获取字符统计结果字符串String recordsByString = getRecordsByString(str);List<String> strsList = hashString.getOrDefault(recordsByString, new ArrayList<>());strsList.add(str);    // 将其添加到哈希表的值中hashString.put(recordsByString, strsList);}return new ArrayList<>(hashString.values());    // 将哈希表中的结果返回}// 对字符串出现的字符及数量进行统计// 将统计的字符 及其数目 拼接成字符串返回public String getRecordsByString(String str) {int[] records = new int[26];int len = str.length();for (int i = 0; i < len; ++i) {records[ str.charAt(i) - 'a' ] ++;}StringBuilder sb = new StringBuilder();for (int i = 0; i < 26; ++i) {if (records[i] != 0) {sb.append(i+'a');sb.append(records[i]);}}return sb.toString();}
}

提交结果如下：

解答成功:执行耗时:9 ms,击败了30.66% 的Java用户内存消耗:46 MB,击败了19.57% 的Java用户

复杂度分析：

• 时间复杂度：$O(n(k+|\Sigma |))$，n为数组strs的长度，k是strs中字符的最大长度，$|\Sigma |=26$，遍历每个字符串时，还需要遍历一遍统计数组，其长度为26

• 空间复杂度：$O(n(k+|\Sigma |))$，需要用哈希表来存储，n为数组strs长度，k则是字符串的长度，此外还有生成的哈希表的键

这篇关于LC 49.字母异位词分组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---