高效分组变位词：无需排序的哈希映射方法

碧海醫心

发布时间：2025-10-14 11:29:22

470人浏览过

来源于php中文网

原创

高效分组变位词：无需排序的哈希映射方法

本文详细介绍了在leetcode中无需对字符串进行排序，通过字符频率统计实现高效分组变位词（anagrams）的算法。文章将深入解析核心思路、代码实现细节，并对该方法的关键步骤和时间复杂度进行专业分析，帮助读者理解如何利用哈希映射优化变位词分组问题。

变位词分组问题概述

变位词（Anagrams）是指由相同字母但顺序不同的字符串组成的词语，例如 "eat"、"tea" 和 "ate" 互为变位词。在编程中，一个常见的问题是将一组字符串按照它们是否为变位词进行分组。传统方法通常涉及对每个字符串进行排序，然后将排序后的字符串作为哈希表的键。然而，本文将探讨一种无需排序，通过字符频率统计实现的高效方法。

基于字符频率统计的解决方案

该解决方案的核心思想是为每个字符串创建一个唯一的“签名”，这个签名能够代表其包含的字符种类和数量，而与字符的排列顺序无关。所有互为变位词的字符串，都将拥有相同的签名。我们将利用哈希映射（HashMap）来存储这些签名作为键，并将对应的变位词列表作为值。

算法步骤详解

初始化结果列表和哈希映射：
- 创建一个 List> 用于存放最终的分组结果。
- 创建一个 Map>，其中键是字符串的字符频率签名，值是属于该签名的字符串列表。
遍历输入字符串数组：
- 对于数组中的每一个字符串 str： a. 创建字符频率数组： 初始化一个长度为 26 的整型数组 int[] input。这个数组的每个索引代表一个英文字母（'a' 到 'z'），对应的值表示该字母在当前字符串中出现的次数。 b. 填充频率数组： 遍历当前字符串 str 的每一个字符。对于每个字符 c，通过 c - 'a' 计算其在数组中的索引，并将对应位置的值加一。例如，如果字符是 'e'，则 input['e' - 'a'] 的值会增加。 c. 生成字符串签名： 将这个 int[26] 频率数组转换为一个字符串表示。Java 的 Arrays.toString(int[]) 方法可以方便地完成此操作，它会生成形如 "[1, 0, 0, 0, 1, 0, ..., 1, 0]" 的字符串。这个字符串就是当前字符串的唯一签名。
  - 关键理解点： 无论 "eat"、"tea" 还是 "ate"，它们在经过字符频率统计后，都会得到相同的频率数组（例如，'a' 出现 1 次，'e' 出现 1 次，'t' 出现 1 次，其他字母出现 0 次）。因此，Arrays.toString() 转换后得到的字符串签名也将完全相同。这使得我们能够将互为变位词的字符串映射到同一个键下。 d. 更新哈希映射：
  - 检查哈希映射 outputMap 中是否已存在以 inputStr（即频率数组的字符串签名）为键的条目。
  - 如果存在，说明之前已经处理过与当前字符串互为变位词的字符串，直接将当前字符串 str 添加到该键对应的列表中。
  - 如果不存在，说明这是第一次遇到这种字符组合，创建一个新的 ArrayList，将当前字符串 str 添加进去，然后将这个新的列表以 inputStr 为键存入 outputMap。
收集结果：
- 遍历完所有输入字符串后，哈希映射 outputMap 中的每个值（即 List）都代表一个变位词分组。将 outputMap.values() 中的所有列表添加到最终的结果列表 output 中。

示例代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GroupAnagrams {

    public List> groupAnagrams(String[] strs) {
        List> output = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return output;
        }

        // 使用哈希映射存储频率签名到字符串列表的映射
        Map> outputMap = new HashMap<>();

        // 遍历所有输入字符串
        for (String str : strs) {
            // 1. 创建字符频率数组
            int[] charCounts = new int[26]; // 对应 'a' 到 'z'

            // 2. 填充频率数组
            for (char c : str.toCharArray()) {
                charCounts[c - 'a']++;
            }

            // 3. 生成字符串签名（将频率数组转换为字符串）
            String signature = Arrays.toString(charCounts);

            // 4. 更新哈希映射
            // 如果签名已存在，则将当前字符串添加到对应的列表中
            // 否则，创建一个新列表并存入哈希映射
            outputMap.computeIfAbsent(signature, k -> new ArrayList<>()).add(str);

            // 等价于以下传统写法：
            // if (outputMap.containsKey(signature)) {
            //     outputMap.get(signature).add(str);
            // } else {
            //     List newList = new ArrayList<>();
            //     newList.add(str);
            //     outputMap.put(signature, newList);
            // }
        }

        // 5. 收集结果
        output.addAll(outputMap.values());
        return output;
    }

    public static void main(String[] args) {
        GroupAnagrams solver = new GroupAnagrams();
        String[] strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List> result1 = solver.groupAnagrams(strs1);
        System.out.println("Result 1: " + result1); 
        // 预期输出可能类似：[[bat], [nat, tan], [eat, tea, ate]] (顺序可能不同)

        String[] strs2 = {""};
        List> result2 = solver.groupAnagrams(strs2);
        System.out.println("Result 2: " + result2); // 预期输出：[[]] 或 [[ ]]

        String[] strs3 = {"a"};
        List> result3 = solver.groupAnagrams(strs3);
        System.out.println("Result 3: " + result3); // 预期输出：[[a]]
    }
}

注意事项

字符集限制： 此方法假设输入字符串只包含小写英文字母。如果包含大写字母、数字或其他字符，需要调整频率数组的大小（例如 256 来覆盖所有 ASCII 字符）以及字符到索引的映射方式。
Arrays.toString() 的开销： 尽管 Arrays.toString() 需要遍历整个数组，但由于频率数组的大小固定为 26，这个操作的时间复杂度是常数级的 O(1)。
哈希冲突： HashMap 在内部处理哈希冲突，其平均操作时间复杂度为 O(1)。

时间复杂度分析

我们来详细分析上述算法的时间复杂度。假设输入字符串数组的长度为 m (即 strs.length)，平均每个字符串的长度为 n。

外层循环： 算法包含一个主循环，它会遍历 strs 数组中的每一个字符串，共执行 m 次。

LogoMaker
免费在线制作Logo，在几分钟内完成标志设计

下载
内层操作（针对每个字符串）：
- 创建并填充 charCounts 数组： 对于每个字符串，我们需要遍历其所有字符来统计频率。这个操作的时间复杂度是 O(n)，其中 n 是当前字符串的长度。
- 调用 Arrays.toString(charCounts)： 这个方法会将长度为 26 的 charCounts 数组转换为字符串。由于数组长度是固定的常数（26），此操作的时间复杂度可以视为 O(1)。
- 哈希映射操作： outputMap.computeIfAbsent()（或 containsKey()、get()、put()）这些哈希映射操作在平均情况下具有 O(1) 的时间复杂度。
总时间复杂度计算：
- 外层循环执行 m 次。
- 在每次外层循环中，我们执行一个 O(n) 的操作（填充频率数组）和几个 O(1) 的操作（Arrays.toString 和哈希映射操作）。
- 因此，总的时间复杂度是 m * (O(n) + O(1) + O(1))，简化后为 O(m * n)。
最终结果收集： output.addAll(outputMap.values()) 操作会将所有列表添加到最终结果中。这个操作的复杂度取决于所有列表的总长度，最坏情况下是 O(m * n)，但通常可以视为 O(m) 因为它只是收集指针。不过，它不会超过 O(m * n)。