力扣最热一百题——2.字母异位词分组
目录
题目链接：49. 字母异位词分组 - 力扣（LeetCode）
话不多说直接上题目。
题目链接：49. 字母异位词分组 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
说实话刚刚看到这个题目的时候心中有很多想法，但好像都不是很容易实现，那其实作为力扣的一道中等题，还是存在些许的难度的，我们来看看具体怎么解决它吧。
题目
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]仅包含小写字母
解法一：哈希表+排序
思路
我们的目标是对给定字符串数组中的异位词进行分组的。第一种解法的思路如下。
首先定义一个结果容器res，用来存放分组后的结果。然后定义一个哈希表map作为哈希表，其中每个键是按照字母顺序排序后的字符串，对应的值是该异位词的全部字符串。
接下来，代码通过遍历给定的字符串数组strs，对每个字符串进行处理。首先将字符串转换为字符数组chars，然后对字符数组进行排序，得到按照字母顺序排序后的字符串s。然后从map中取出以s为键的值，如果不存在则使用默认值new ArrayList<String>()创建一个空的ArrayList。然后将当前的字符串str加入到该ArrayList中，并将更新后的ArrayList再次放入map中。这样就完成了将同一组异位词存放在同一个键下的操作。
最后，通过调用map的values()方法获取所有值的集合，并使用ArrayList的构造函数将其转换为ArrayList返回即可。
其实还是非常的简单的。
代码实现
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 定义出返回的list容器
List<List<String>> res = new ArrayList<>();
// 定义map集合作为哈希表,排序后的字符串作为key，该异位词的全部作为value
Map<String, ArrayList<String>> map = new HashMap<>();
// 遍历挨个取出数组中的字符串
for (String str : strs) {
// 将字符串转换为字符数组便于将字母排序
char[] chars = str.toCharArray();
// 排序
Arrays.sort(chars);
String s = new String(chars);
// 加入进value
ArrayList<String> orDefault = map.getOrDefault(s, new ArrayList<String>());
orDefault.add(str);
map.put(s, orDefault);
}
return new ArrayList<>(map.values());
}
}注意：这里不能直接使用排序后的字符数组来作为key，因为直接使用字符数组是使用的地址，会导致即使是一样的字符数组也会是不同的哈希值，所以不可以让字符数组作为key。
解法二：记录字母出现的次数+哈希表
思路
我们的目的是将给定字符串数组中的异位词进行分组的。与之前的代码相比，这里使用了记录字母出现次数加哈希表的方法。
首先定义一个哈希表map，其中每个键是按照字母出现次数和顺序拼接后的字符串，对应的值是该异位词的全部字符串。
然后，遍历给定的字符串数组strs，对每个字符串进行处理。首先定义一个长度为26的整型数组counts，用来统计每个字母出现的次数。然后遍历字符串的每个字符，根据字符与字母'a'的差值来确定在counts数组中的位置，并将对应位置的计数值加1。
接下来，使用StringBuffer对出现次数大于0的字母和对应的出现次数进行拼接，得到按顺序拼接后的字符串sbuf，作为哈希表的键。然后从map中取出以sbuf为键的值，如果不存在则使用默认值new ArrayList<>()创建一个空的ArrayList。然后将当前的字符串str加入到该ArrayList中，并将更新后的ArrayList再次放入map中。这样就完成了将同一组异位词存放在同一个键下的操作。
最后，通过调用map的values()方法获取所有值的集合，并使用ArrayList的构造函数将其转换为ArrayList返回即可。
代码实现
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 这次采用记录出现字母的次数加哈希表的方法
Map<String, List<String>> map = new HashMap<>();
// 遍历取出每个字符串
for (String str : strs) {
// 定义一个长度为26的整形数组，0代表a，1代表b以此类推
int[] counts = new int[26];
// 统计字母出现的次数
int length = str.length();
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的key
// 采用StringBuffer进行拼接
StringBuffer sbuf = new StringBuffer();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
// 这里是将对应的字母和出现次数直接拼接了，而不是出现多少次拼接多少次
sbuf.append((char) ('a' + i));
sbuf.append(counts[i]);
}
}
// 转换为字符串作为key
String key = new String(sbuf);
List<String> list = map.getOrDefault(key, new ArrayList<>());
list.add(str);
map.put(key, list);
}
return new ArrayList<>(map.values());
}
}注意：
sbuf.append((char) ('a' + i));
sbuf.append(counts[i]);这两行代码是用来将出现次数大于0的字母和对应的出现次数拼接成一个字符串sbuf。
sbuf.append((char) ('a' + i)): 这行代码将当前字母的ASCII码转换为对应的字符，并将其追加到sbuf中。因为字母'a'对应的ASCII码是97，所以通过('a' + i)可以得到对应的字母。sbuf.append(counts[i]): 这行代码将counts数组中当前字母的出现次数追加到sbuf中，以便形成完整的拼接字符串。
也就是说：这里是将对应的字母和出现次数直接拼接了，而不是出现多少次拼接多少次
因为多了很多需要遍历操作还开了很多内存，所以执行速度和内存消耗都有点不尽人意，记住第一种方法就好。
总结
其实还是挺EZ的，哈希表的题目都挺简单的，就是存和找的过程罢了。
原文地址：https://blog.csdn.net/DDDDWJDDDD/article/details/140606326
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！