力扣49-字母异位分组
一、原题题目
1.1 题目
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
1.2 示例
示例1:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
说明:
所有输入均为小写字母。
不考虑答案输出的顺序。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/group-anagrams/
二、解题思路一
2.1 题目意思理解
这道题题目意思比较简单,即单词的字母组成上相同的但排列顺序不同的分为一个组,遍历每一个单词和保存结果lists中的每一个组中单词是不是异位的,是则加入改组,不是则判断下一组,直到遍历完存在的所有组,则创建一个新组加入。
2.2 详细代码(Java)
public class Solution {
public static List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> lists = new ArrayList<>(); // 定义保存结果的 lists
for (int i = 0;i<strs.length;i++){ // 遍历每一个单词
boolean flag = false; // 记录是否有加入已经存在的组
for (List<String> list : lists) { // 遍历lists中的每一个组
if (isSameWords(strs[i],list.get(0))) { // 判断当前组的第一个单词和遍历的单词是否异位
list.add(strs[i]); // 是异位则加入该组
flag = true; // 状态改为已加入组的状态
continue; // 跳过后面的组
}
}
if (flag == false) { // 没有加入组,说明没有与任何已经存在的组异位,自己独自建组加入lists
List<String> list = new ArrayList<>();
list.add(strs[i]);
lists.add(list);
}
}
return lists; // 最终返回lists
}
public static boolean isSameWords(String word1,String word2){ // 判断两个单词是否异位
if (word1.length()!= word2.length()) return false;
char[] chars1 = word1.toCharArray();
char[] chars2 = word2.toCharArray();
Arrays.sort(chars1);
Arrays.sort(chars2);
return String.valueOf(chars1).equals(String.valueOf(chars2));
}
}
2.3 算法执行结果

结果比较惨,但还好也是自己很快就相处来的方法,接着再思考思考提升下性能。
三、解题思路二(哈希表)
3.1 题目意思理解
大概意思跟上一种思路一致,用哈希表来存储结果,每一个单词先转换成字符数组,然后排序,再把排序后的字符数组转换成字符串作为同类异位单词的 key ,组作为 value。例如示例:[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],对于 “eat” 和 “tea” 单词他们转化求 key 都是 “aet” ,即属于同一个组。
3.2 详细代码(Java)
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String,List<String>> hashMap = new HashMap<>(); // 定义哈希表存储分组结果
for (int i =0 ;i<strs.length;i++){ // 遍历每一个单词
char[] chars = strs[i].toCharArray(); // 单词转换成字符数组
Arrays.sort(chars); // 对单词字符数组排序
String key = new String(chars); // 得到单词对应的 key
if (hashMap.containsKey(key)){ // 如果这个 key 在哈希表中存在
List<String> list = hashMap.get(key); // 取出 key 对应的组
list.add(strs[i]); // 将该单词加入到这个组
}
else { // 如果这个 key 在哈希表中不存在
ArrayList<String> list = new ArrayList<>(); // 要新创建一个组
list.add(strs[i]); // 新创建的组中加入该单词
hashMap.put(key,list); // 新创建的组加入哈希表中
}
}
List<List<String>> result = new ArrayList<>(hashMap.values()); // 哈希表值的部分转换成需要输出的格式
return result;
}
}
3.3 算法执行结果

这个结果还行,两种方法思路上差别还是存在很大差距的,哈希表的运用大幅度提升了性能。