LeetCode_字符串_中等_49.字母异位词分组

今天药忘吃喽~ 2023-10-06 18:41 32阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。  
字母异位词指字母相同，但排列不同的字符串。

**示例 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\] 仅包含小写字母

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/group-anagrams

## 2.思路 ##

（1）HashMap & 排序  
经过分析题目后可知，本题的难点在于**以何种判断依据将字母异位词组合一起**，这里考虑使用 HashMap & 排序的方法：

*  遍历整个字符串数组，对于每一个字符串 strs\[i\]，将其转换为字符数组并进行排序，然后**将排序后的字符数组转换为对应的字符串 strKey，并将其作为 HashMap 的键，用于区分由不同字母排列组成的字符串**；
 *  获取 hashMap 中键为 strKey 的值（即一个 List 数组），如果没有则新建一个 List< String>，然后将当前字符 strs\[i\] 加入其中，最后再将<strKey, list> 存入 hashMap 中（这一操作相当于在更新 hashMap 中键为 strKey 的值，当然如果 hashMap 中暂时还没有键 strKey，则将其本身以及对应的值添加进 hashMap 即可）；
 *  字符串数组遍历完成后，hashMap 中的所有键所对应的值所组成的集合即为题目要求的答案，将其返回即可。

（2）计数

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

## 3.代码实现（Java） ##

//思路1————HashMap & 排序
    class Solution {
        
        public List<List<String>> groupAnagrams(String[] strs) {
        
            Map<String, List<String>> hashMap = new HashMap<String, List<String>>();
            for (String str : strs) {
        
                //将当前字符串 strs[i] 转换为字符数组
                char[] array = str.toCharArray();
                //对字符数组进行排序
                Arrays.sort(array);
                //将排序后的字符数组转换为对应的字符串，并将其作为 HashMap 的键，用于区分由不同字母排列组成的字符串
                String strKey = new String(array);
                //获取 hashMap 中键为 strKey 的值，如果没有则返回 new ArrayList<String>()
                List<String> list = hashMap.getOrDefault(strKey, new ArrayList<>());
                list.add(str);
                //put():如果插入的 key 对应的 value 已经存在，则执行替换操作，返回旧的 value 值，如果不存在则执行插入，返回 null
                hashMap.put(strKey, list);
            }
            //将 hashMap 中的值作为结果进行返回
            return new ArrayList<List<String>>(hashMap.values());
        }
    }

//思路2————计数
    class Solution {
        
        public List<List<String>> groupAnagrams(String[] strs) {
        
            Map<String, List<String>> map = new HashMap<>();
            for (String str : strs) {
        
                int[] cnts = new int[26];
                int length = str.length();
                for (int i = 0; i < length; i++) {
        
                    cnts[str.charAt(i) - 'a']++;
                }
                // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
                StringBuffer builder = new StringBuffer();
                for (int i = 0; i < 26; i++) {
        
                    if (cnts[i] != 0) {
        
                        builder.append((char) ('a' + i));
                        builder.append(cnts[i]);
                    }
                }
                String key = builder.toString();
                List<String> list = map.getOrDefault(key, new ArrayList<>());
                list.add(str);
                map.put(key, list);
            }
            return new ArrayList<List<String>>(map.values());
        }
    }