题目
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
- 输入:
["eat", "tea", "tan", "ate", "nat", "bat"], - 输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
分析：字符串分类的题
题目中有很多个word,不同的word中的字符可能是一样的，需要归为一类，可以采用哈希表存储同一类异构字符串的值。
解法1:
- 利用HashMap，存储key
- 将每一个字符串拆分成字符数组，然后，排序，在组装成字符串，这样同字符异构的字符串就变成一样的了
- 利用key就可以查找含有同样字符的字符串了
// java Map API使用注意：getOrDefault(key,default) 的 返回值需要重新put到map中去，否则Map中不存在对应的key-value。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
char[] array = str.toCharArray();
Arrays.sort(array);// 字典排序
String key = new String(array);// 构造key,
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
// 构造二维list并返回
return new ArrayList<List<String>>(map.values());
}
}
解法2:
- 将字符串拆分，然后，将字符串按照一定规则，获得其独有的特点（构造
hashcode）- 统计字符串中每个字母的个数，然后append每个字母的个数，同时加上用特殊字符的分隔符
- 同样利用HashMap的特点
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 空字符集处理
if (strs.length == 0) return new ArrayList<List<String>>();
// 结果集
Map<String,List<String>> map = new HashMap<String,List<String>>();
int[] count = new int[26];
for (int i = 0;i < strs.length;i++) {
// 构造唯一的指纹
Arrays.fill(count,0);
for(char c :strs[i].toCharArray()) count[c-'a']++;// 统计字符
StringBuilder sb = new StringBuilder("");
for (int j = 0;j < 26;j++) {// 构造字符串
sb.append("$");
sb.append(count[j]);
}
String key = sb.toString();// 获得key
if (!map.containsKey(key)) map.put(key,new ArrayList<String>());
map.get(key).add(strs[i]);
}
return new ArrayList<List<String>>(map.values());
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
