非独立思考
常规思路:
- 由于互为字母异位词的两个字符串包含的字母相同,因此对两个字符串分别进行排序之后得到的字符串一定是相同的,故可以将排序之后的字符串作为哈希表的键。
- 由于互为字母异位词的两个字符串包含的字母相同,因此两个字符串中的相同字母出现的次数一定是相同的,故可以将每个字母出现的次数使用字符串表示,作为哈希表的键。
getOrDefault() 方法获取指定 key 对应对 value,如果找不到 key ,则返回设置的默认值。
class Solution {public static List<List<String>> groupAnagrams(String[] strs) {// 因为既有存值,也有查询。所以用Map会好一些// 很多题目可能会有溢出一些问题,在对数据本身没有要求时可以尝试使用高精度型Map<Double, ArrayList<String>> resMap = new HashMap<>(16);Map<Character, Integer> chaMap = new HashMap<>(16);List<Integer> list = has26Prime();char ch = 'a';for (Integer val : list) {// 存入26个字母对应的值chaMap.put(ch, val);ch++;}for (String str : strs) {// 针对每个str,我们再循环去获取他们的乘积// 先获取乘积,再比较mapdouble sum = 1;for (int i = 0; i < str.length(); i++) {sum *= chaMap.get(str.charAt(i));}// 比较,但是不管有没有,都是需要添加进去,只不过没有的时候需要新建if (!resMap.containsKey(sum)) {resMap.put(sum, new ArrayList());}resMap.get(sum).add(str);}return new ArrayList<>(resMap.values());}public static List<Integer> has26Prime() {ArrayList<Integer> list = new ArrayList<>();for (int i = 2; i <= 200; i++) {if (isPrime(i)) {list.add(i);}if (list.size() == 26) {return list;}}return list;}public static boolean isPrime(int n) {for (int i = 2; i <= n / 2; i++) {if (n % i == 0) {return false;}}return true;}}
class Solution {public List<List<String>> groupAnagrams(String[] strs) {HashMap<String, List<String>> map = new HashMap<>(16);for (String str : strs) {char[] chars = str.toCharArray();Arrays.sort(chars);// 这里的key,要么Arrays工具类,要么new String();// char[]的toString默认调用的是Object的toString// return getClass().getName() + "@" + Integer.toHexString(hashCode());String key = Arrays.toString(chars);List<String> list = map.getOrDefault(key, new ArrayList<>());list.add(str);map.put(key, list);}return new ArrayList<List<String>>(map.values());}}
