49. 字母异位词分组

题目：字母异位词分组

描述：

给定一个字符串数组 strs，将字母异位词组合在一起。字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例：

示例 1:

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

示例 2:

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

示例 3:

输入: strs = ["a"]
输出: [["a"]]

---

解题思路：

字母异位词具有相同的字符集合，因此可以通过将字符串排序后得到统一的“代表”来判断字母异位词。这样，所有字母异位词在排序后的字符串中都会映射到同一个值。因此，我们可以使用一个哈希表（HashMap）将排序后的字符串作为键，原始字符串作为值进行分组。

算法步骤：

1. 遍历数组中的每个字符串。
2. 对每个字符串进行排序，将排序后的字符串作为键。
3. 将每个原始字符串添加到对应键的值（列表）中。
4. 最后，返回哈希表中的所有值，即为字母异位词的分组。

代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取字符串数组的长度
        int n = scanner.nextInt();
        scanner.nextLine(); // 消费换行符

        String[] strs = new String[n];

        // 读取每个字符串
        for (int i = 0; i < n; i++) {
            strs[i] = scanner.nextLine();
        }

        Solution solution = new Solution();
        List<List<String>> result = solution.groupAnagrams(strs);

        // 输出结果（格式：[[eat, tea, ate], [tan, nat], [bat]]）
        System.out.print("[");
        for (int i = 0; i < result.size(); i++) {
            System.out.print("[");
            List<String> group = result.get(i);
            for (int j = 0; j < group.size(); j++) {
                System.out.print(group.get(j));
                if (j < group.size() - 1) {
                    System.out.print(", ");
                }
            }
            System.out.print("]");
            if (i < result.size() - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");

        scanner.close();
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 用一个哈希表来存储字母异位词
        Map<String, List<String>> map = new HashMap<>();

        // 遍历每个字符串
        for (String str : strs) {
            // 将字符串转换为字符数组并排序，得到唯一的代表
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);

            // 将原始字符串添加到哈希表对应排序后的字符串键下
            List<String> list = map.getOrDefault(sortedStr, new ArrayList<>());
            list.add(str);
            map.put(sortedStr, list);
        }

        // 返回哈希表中的所有值（即分组后的字母异位词）
        return new ArrayList<>(map.values());
    }
}

时间复杂度分析：

• 时间复杂度：

  • 对每个字符串进行排序，排序的时间复杂度是 O(k log k)，其中 k 是字符串的长度。
  • 遍历所有字符串需要 O(n) 的时间，其中 n 是字符串的数量。
  • 因此，总的时间复杂度为：O(n * k log k)，其中 n 是字符串的数量，k 是单个字符串的最大长度。

• 空间复杂度：

  • 我们使用哈希表存储所有字符串，因此空间复杂度为 O(n * k)，其中 n 是字符串的数量，k 是字符串的最大长度。

结论：

这个解法通过对每个字符串排序并使用哈希表进行分组，能够有效地将字母异位词分组在一起，时间复杂度也比较合理，可以应对中等规模的数据集。

---