力扣热题100刷题day63|49.字母异位词分组

目录

一、哈希表相关理论

二、思路

核心思路

三、相关题目

四、总结

---

一、哈希表相关理论

代码随想录刷题day15|（哈希表篇）242.有效的字母异位词、383.赎金信-CSDN博客

二、思路

首先，创建一个map集合，遍历字符串数组，对数组中每一个字符串（单词）比如"abc" 进行如下操作：创建一个长度为26的数组count，遍历当前字符串，计算出每个字母出现的次数，用count来存储元素中每个字母出现的次数，之后将数组count转换成对应字符串（通过sb，添加数组元素，然后toString）；

map集合中的键就存放该频率字符串，也就是"1#1#1#0#...." （以"abc"为例）；

map集合中键对应的值则存放 当前遍历（操作）的原数组中的字符串（字母）即 "abc"；所以值的类型是列表 list<String>；

“abc” ---> [1,1,1,0,0.....] --->“#1#1#1#0.....”=key

map中添加的逻辑是：首先 判断该key是否存在，如果不存在，则创建一个ArrayList对象，如果存在，无需创建；

不管key存不存在，都要再将当前 处理的字符串“abc” 添加到list列表中["abc","acb","bca"]；

那么最终，map中所有的值value 就是所有的字母异位词的分组，比如：

key:“#1#1#1#0.....”    value:["abc","acb","bca"]

key:"#0#1#1#1#0..."  value:["bcd","bdc","cdb"]

.......

最后获取map中的所有值的集合map.values()，返回（Collection<List<String>>）；

也就是值是什么类型 外层再加一个collection；

new ArrayList<>(...)    将 Collection 转换为 List，确保返回类型正确且可修改；

核心思路

1. 字母计数：

   • 为每个单词创建一个长度为26的数组，统计每个字母出现的次数

   • 例如："aab" → [2,1,0,0,...,0]（a出现2次，b出现1次）

2. 生成唯一键：

   • 将计数数组转换为不可变的数据结构（如元组或字符串）作为哈希表的键

   • 例如：[2,1,0,...] → 转换为元组 (2,1,0,...) 或字符串 "2#1#0#..."

3. 哈希表分组：

   • 使用这个键将原始单词分组存储

三、相关题目

49.字母异位词分组

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for(String str : strs){int[] count = new int[26];for(char c : str.toCharArray()){//int[] count = new int[26];count[c - 'a']++;}StringBuilder sb = new StringBuilder();for(int i : count){sb.append("#");sb.append(i);}String k = sb.toString();if(!map.containsKey(k)){List<String> list = new ArrayList<>();map.put(k, list);}map.get(k).add(str);}return new ArrayList<>(map.values());}}

四、总结

本题和有效的字母异位词不太一样，因为涉及到分组，怎么分组，怎么得到分组后的最终结果，但是最初处理字母异位词的逻辑相同，均使用数组；

还有最后的map集合put键值对的逻辑，如果按照下面的写法：

String k = sb.toString();
if(!map.containsKey(k)){//map中不包含kList<String> list = new ArrayList<>();list.add(str);map.put(k, list);
}

错因：只在key不存在时添加字符串，这样会漏掉后续相同key的字符串；

每次遇到一个字符串时，都创建了一个新的 ArrayList 并覆盖了 Map 中已有的值，这样会导致之前的同组异位词被覆盖丢失；

只有当key不存在时才创建新list；

无论key是否存在，都要将当前字符串添加到对应的list中；