49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
题解：
本体主要考察的是对hashmap的用法：
首先，看到了字母排序不同我们就可以猜想到用hashmap，那么如何用hashmap来解决这个问题呢？我们可以对字符串中各字母的个数进行计数，如果每个字母出现的次数都一样则代表两个字符串是异位词。
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<>();
HashMap<HashMap<Character, Integer>, List<String>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
String str = strs[i];
HashMap<Character, Integer> characterIntegerHashMap = scanWord(str);
if (!map.containsKey(characterIntegerHashMap)) {
map.put(characterIntegerHashMap, new ArrayList<>());
}
map.get(characterIntegerHashMap).add(str);
}
for (List list:
map.values()) {
result.add(list);
}
return result;
}
private HashMap<Character, Integer> scanWord(String str) {
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) + 1);
}
return map;
}
这种方法效率有点低，而且内存占用也高。
还有一种方法就是对字符串的字符排序，然后进行比较。
public List<List<String>> groupAnagrams2(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] chars = strs[i].toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List<String> list = map.getOrDefault(key, new ArrayList<>());
list.add(strs[i]);
map.put(key, list);
}
return new ArrayList<>(map.values());
}
总而言之，都是对hashmap使用的考察。
本题出自leetcode：https://leetcode-cn.com/problems/group-anagrams/
