Java 实现 字母异位词分组

在这篇博客中，我们将详细解析如何使用 Java 代码来解决 字母异位词分组这个经典的算法问题。我们会逐步分析代码逻辑，并探讨其时间复杂度及优化思路。

题目描述

给定一个字符串数组 strs，请将字母异位词组合在一起。字母异位词是指由相同字母组成但顺序不同的字符串。例如：

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

代码实现

我们可以使用 哈希表 + 排序  来解决这个问题，代码如下：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建一个哈希表，用于存储归类后的异位词组
        Map<String, List<String>> map = new HashMap<>();
        
        // 遍历字符串数组
        for (int i = 0; i < strs.length; i++) {
            String s = strs[i];
            
            // 将字符串转换为字符数组，并排序
            char[] ch = s.toCharArray();
            Arrays.sort(ch);
            
            // 将排序后的字符数组转换回字符串作为哈希表的 key
            String key = new String(ch);
            
            // 获取当前 key 对应的列表（如果不存在则创建新的列表）
            List<String> li = map.getOrDefault(key, new ArrayList<>());
            
            // 将当前字符串加入列表
            li.add(s);
            
            // 更新哈希表
            map.put(key, li);
        }
        
        // 返回哈希表中所有值组成的列表
        return new ArrayList<>(map.values());
    }
}

代码解析

1. 使用哈希表进行分组

• 核心思想：字母异位词排序后得到的字符串是相同的，我们可以利用这个特性，将其作为哈希表 map 的键（key），对应的值（value）是属于该类的字符串列表。

• 哈希表结构：

  {
      "aet": ["eat", "tea", "ate"],
      "ant": ["tan", "nat"],
      "abt": ["bat"]
  }
  

2. 遍历字符串数组

• 遍历输入的 strs 数组，对每个字符串：

  1. 将其转换为字符数组并排序。

  2. 排序后的结果作为 key，存入 map 中。

  3. 若 key 已存在，则添加到对应的 List；若不存在，则新建 List。

3. 返回最终结果

• map.values() 存储了所有的分组，因此我们返回 new ArrayList<>(map.values())。

时间复杂度分析

1. 排序时间复杂度

• 每个字符串需要排序，假设字符串的最大长度为 K，那么排序的时间复杂度是 O(K log K)。

2. 遍历字符串数组

• 假设字符串数组的大小是 N，那么遍历 N 个字符串的时间复杂度是 O(N)。

3. 总体时间复杂度

• 由于我们需要对 N 个字符串进行排序，每个排序的复杂度为 O(K log K)，总的时间复杂度为：

  O(N * K log K)
  

  其中：

  • N 是字符串数组的大小

  • K 是字符串的平均长度

优化思路

1. 使用字符计数代替排序

   • 我们可以用长度为 26 的整数数组（表示 a-z 的频次）作为 key，而不是排序后的字符串。

   • 这样可以避免 O(K log K) 的排序时间，将其优化为 O(K)。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strs) {
            // 统计字符出现频率
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            
            // 生成唯一的 key
            String key = Arrays.toString(count);
            
            // 存入哈希表
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(map.values());
    }
}

新方法的时间复杂度

• 由于 Arrays.toString(count) 生成的 key 长度固定为 26（英文字母个数），其构建的时间复杂度是 O(1)。

• 整体时间复杂度降低为 O(NK)，比 O(NK log K) 更高效。

总结

• 本文详细解析了 字母异位词分组 问题，并使用 排序 + 哈希表 进行求解。

• 时间复杂度为 O(NK log K)。

• 通过 字符计数法，可以进一步优化到 O(NK)。

• 这是一道典型的哈希表应用题目，考察了字符串处理和数据结构的使用。

希望本文能帮助你更好地理解该问题！如果有任何疑问或优化建议，欢迎交流讨论！🎯