力扣题解49. 字母异位词分组
题目
力扣hot100中的第二题
简言之就是找传进来的字符串数组中字母数量一样的组合在一起并返回.
想解决这题我们需要解决一个问题:我们如何判断她们是异位词?
有两种解法:一:通过计算字母出现的次数来判断 二:将字母排序后比较.
解法一:
class Solution {
public List> groupAnagrams(String[] strs) {
Map> map = new HashMap>();
for (String str : strs) {
int[] counts = new int[26];
int length = str.length();
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counts[i]);
}
}
String key = sb.toString();
List list = map.getOrDefault(key, new ArrayList());
list.add(str);
map.put(key, list);
}
return new ArrayList>(map.values());
}
}
由于此解法效率不太行,不做过多介绍
解法二:排序
有if版本(方便理解)
class Solution {
public List> groupAnagrams(String[] strs) {
Map> map=new HashMap<>();
for (String str : strs) {
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String sortStr = new String(charArray);
if (map.containsKey(sortStr)){
List list = map.get(sortStr);
list.add(str);
}else {
map.put(sortStr, new ArrayList<>(Collections.singleton(str)));
}
}
return new ArrayList<>(map.values());
}
} 我们先声明一个哈希表,其中key为排序后的字母组,value为未排序的字母组.我们没次进哈希表中查找,如果查找到了,我们先声明List来接收,然后在其中添加就行(注意:我们不需要再把list在传进map因为我们是声明一个list接收的,是一个指针的效果),如果没有,我们new一个list并将Str传入
String sortStr = new String(charArray);
相比与运用工具类上面的写法会更快!!!
无if版本(速度更快)
class Solution {
public List> groupAnagrams(String[] strs) {
Map> map=new HashMap<>();
for (String str : strs) {
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String sortStr=new String(charArray);
List list = map.getOrDefault(sortStr, new ArrayList());
list.add(str);
map.put(sortStr,list);
}
return new ArrayList<>(map.values());
}
} 注意:这里每个list都要进行put操作
