049.字母异位词分组

作者：沉默王二
发布时间：2024-09-20T09:59:45.371+0800

鲁迅曾逼逼：老虎说草原是绿色的，驴子说草原是蓝色的，两人争论不休，于是就找到狮子法官理论，结果狮子判老虎禁闭三天好好反思一下，因为他把时间浪费在了一件毫无意义的事情上。这件事的寓意其实很朴素，不要争论，如果别人觉得自己是对的，那你就对对对三连。把时间真正用到有意义的事情上，比如刷二哥的 LeetCode 题解。

题意

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

难度

中等

示例

示例 1:

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: strs = [""]
输出: [[""]]

示例 3:

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: strs = ["a"]
输出: [["a"]]
### 分析

这道题的重点是理解什么是字母异位词，简单点说，就是每个字母出的次数都一样的字符串。

也就是说，如果两个字符互为 字母异位词，那么分别对它们进行排序后，必然是两个相同的字符串。

我们可以借助这一特性，将每个字符串按照字符排序后作为哈希表的键，然后将相同键的字符串归为一组。

如果看过 HashMap 的源码，其实就能找到类似的感觉，哈希相同的时候会使用拉链法将 key 相同的归为一组，放在链表中。

初始化一个哈希表 map，其中键是排序后的字符串，值是对应的异位词列表（ArrayList ）。

遍历输入数组中的每一个字符串，对字符串中的字符进行排序，然后将排序后的字符串作为键，将原始字符串添加到该键对应的列表中。

遍历完成后，哈希表中的每个键对应的值就是一个字母异位词组。

返回哈希表中的所有值（即字母异位词分组）。

来看题解：

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
import java.util.*;

public class Solution {
public List<List> groupAnagrams(String[] strs) {
// 创建哈希表，键是排序后的字符串，值是异位词列表
Map<String, List> map = new HashMap<>();

    // 遍历每一个字符串
    for (String str : strs) {
        // 将字符串转换为字符数组并排序
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        String sortedStr = new String(charArray); // 将排序后的字符数组转回字符串
        
        // 将排序后的字符串作为键，原始字符串添加到对应的列表中
        if (!map.containsKey(sortedStr)) {
            map.put(sortedStr, new ArrayList<>());
        }
        map.get(sortedStr).add(str); // 添加异位词到列表中
    }
    
    // 返回哈希表中的所有值，即所有异位词分组
    return new ArrayList<>(map.values());
}

public static void main(String[] args) {
    Solution solution = new Solution();
    String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
    List<List<String>> result = solution.groupAnagrams(strs);
    System.out.println(result); // 输出 [["eat","tea","ate"], ["tan","nat"], ["bat"]]
}

}

其中 str.toCharArray() 可以将字符串转换为字符数组，Arrays.sort(charArray) 可以对字符数组进行排序，new String(charArray) 可以将字符数组重新转换为字符串。

map.containsKey(sortedStr) 可以判断哈希表中是否包含某个键，map.put(sortedStr, new ArrayList<>()) 可以将一个空的 ArrayList 添加到哈希表中，map.get(sortedStr).add(str) 可以将异位词添加到相同 key 的列表中。

map.values() 可以获取哈希表中的所有值，返回类型是 Collection，我们可以通过 new ArrayList<>(map.values()) 将其转换为 ArrayList。