LeetCode算法题：49. 字母异位词分组（Java）

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

我的解题思路：
自定义一个hash方法，将每个字符串进行hash计算，将相同hash值的字符串存放在一个list当中。
我定义的hash方法：每个字符的转为int值，然后相乘，乘积对他们的和+1取余数。

出现错误：

原因:上述hash方法存在碰撞，没有有效处理碰撞的情况。
试了好几次自定义的hash方法，一直都是存在碰撞的情况。
不死磕，直接看官方题解：
官方题解1：
方法一：排序
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

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);List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);map.put(key, list);}return new ArrayList<List<String>>(map.values());}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法2：
方法二：计数
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。

由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26的数组记录每个字母出现的次数。需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<String, List<String>>();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<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);map.put(key, list);}return new ArrayList<List<String>>(map.values());}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

自我总结:
对于hash类题目，还是尽量不要自己创建hash方法去计算hash值，你以为的独一无二的hash方法，总能被测试用力暴捶。尽量从题目描述中去找到一些独特之处作为hashmap的键。例如这一次使用排序后的字符串，或者每个字符出现的次数都可以作为键。

如何在函数方法上新建对象？
直接和新建对象一样的方法：new

HashMap的contain方法有哪些。
containsKey(),containsValue()

如何收集HashMap的所有value值作为一个集合返回。

new ArrayList<T>(map.values()) // T与map的value类型要统一

HashMap根据键取值的方法.

map.get(key)

List list = new List();错误的定义集合方法，因为List是一个接口，不能有实现类。

List集合修改某个位置的值

list.set(index,newValue);

字符串转为字符数组的方法

char[] charArray = str.toCharArray();