哈希-03-字母异位词分组

文章目录

• 1. 题目描述
• 2. 思路及代码
• • 错误示例1：
  • 错误示例2：
  • 正确示例：
• 总结

1. 题目描述

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

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
解释：

• 在 strs 中没有字符串可以通过重新排列来形成 “bat”。
• 字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
• 字符串 “ate” ，“eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [“”]
输出: [[“”]]

示例 3:

输入: strs = [“a”]
输出: [[“a”]]

提示：

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

2. 思路及代码

错误示例1：

存在的问题：无法处理多个相同字符的情况，对空字符也处理不了。

publicList<List<String>>groupAnagrams(String[]strs){Set<Set<Character>>sets=newHashSet<>();for(Stringstr:strs){char[]charArray=str.toCharArray();Set<Character>set=newHashSet<>();for(charc:charArray){set.add(c);}sets.add(set);}List<List<String>>lists=newArrayList<>();for(Set<Character>set:sets){List<String>list=newArrayList<>();for(Stringstr:strs){char[]charArray=str.toCharArray();intcount=0;for(charc:charArray){if(set.contains(c)){count++;}}if(count==set.size()){list.add(str);}}lists.add(list);}returnlists;}

错误示例2：

存在的问题：int[]没有重写equals方法，HashSet无法去重！！！会导致出现重复的分组

publicList<List<String>>groupAnagrams2(String[]strs){HashSet<int[]>sets=newHashSet<>();for(Stringstr:strs){int[]ints=newint[26];char[]charArray=str.toCharArray();for(charc:charArray){intascii=c-'a';ints[ascii]+=1;}sets.add(ints);}List<List<String>>lists=newArrayList<>();for(int[]set:sets){List<String>list=newArrayList<>();for(Stringstr:strs){int[]ints=newint[26];char[]charArray=str.toCharArray();for(charc:charArray){intascii=c-'a';ints[ascii]+=1;}if(set.equals(ints)){list.add(str);}}lists.add(list);}returnlists;}

正确示例：

• 使用HashMap + List/Set处理一对多关系。

publicList<List<String>>groupAnagrams3(String[]strs){Map<String,List<String>>map=newHashMap<>();for(Stringstr:strs){char[]charArray=str.toCharArray();Arrays.sort(charArray);//如果key不存在就创建新List，然后添加元素map.computeIfAbsent(String.valueOf(charArray),k->newArrayList<>()).add(str);}Collection<List<String>>values=map.values();returnnewArrayList<>(values);}

总结

1. HashSet无法对没有重写equals方法的数据结构进行去重。
2. 异位词所涉及的字符不变，只是不同的组合，可以用一对多的数据结构来存储。

以上为个人学习分享，如有问题，欢迎指出：）