当前位置：首页 > article >正文

Leetcode 49: 字母异位词分组

article 2025/3/5 2:58:37

Leetcode 49: 字母异位词分组

这是一道经典的哈希表与字符串操作相关的题目，考察快速分组和使用数据结构的能力。所谓字母异位词，是指由相同的字母通过重新排列形成的不同单词。题目要求将一组字符串按照字母异位词分组。

问题描述

给定一个字符串数组 strs，将词组按照字母异位词进行分组，返回所有分组后的结果。字母异位词具有相同的字符，只是排列顺序不同。

输入输出示例：

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

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

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

适合面试的解法：排序 + 哈希表

解法描述

核心思想：将异位词转化为相同的“特征 key”
- 当两个字符串是异位词时，经过 字母排序 后，它们会转换成相同的字符串。例如：
  - "eat" 和 "tea" 排序后都变成 "aet"。
- 我们可以用排序后的字符串作为 哈希表的 key。
实现方式：
- 对数组中的每个字符串进行排序；
- 将排序后的字符串作为哈希表的 key；
- 将原始字符串追加到对应的 key 所表示的列表中。
为什么适合面试？
- 逻辑清晰，不涉及复杂技巧。
- 可以快速实现，直接解决问题。

代码模板

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 使用一个哈希表存储分组结果
        Map<String, List<String>> map = new HashMap<>();

        // 遍历数组中的每个字符串
        for (String s : strs) {
            // 对字符串排序
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);

            // 将排序后的字符串作为 key 插入哈希表
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }

        // 返回哈希表中所有的值
        return new ArrayList<>(map.values());
    }
}

复杂度分析

时间复杂度：
- 遍历所有字符串：O(N)，N 是字符串数组的长度。
- 对每个字符串排序：O(K log K)，K 是每个字符串的平均长度。
- 总复杂度：O(N * K log K)。
空间复杂度：
- 哈希表存储所有字符串，每个字符串最多需要存储一次，因此是 O(N * K)。

适用场景

面试推荐解法： 逻辑简单清晰，容易快速实现。
基于排序的方式适合用来处理字母异位词，无法修改原始字符串的情况下效果较好。

解法 2：计数特征 + 哈希表

解法描述

核心思想：用字符计数数组代替排序
- 对于异位词，其字符的频率分布是相同的。例如：
  - "eat" 和 "tea" 的字母分布均为 {e:1, a:1, t:1}。
- 可以用一个固定大小为 26 的数组（代表英文字母）来统计每个字母的频率。
- 将频率数组转换为字符串作为哈希表的 key。
实现方式：
- 遍历每个字符串，统计其字符频率。
- 构造哈希表，以字符频率数组的字符串表示作为 key。
- 将具有相同字符频率的字符串分组。
优化点：
- 避免了排序操作，相当于将 O(K log K) 降低到 O(K)。

代码模板

import java.util.*;

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
            StringBuilder keyBuilder = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                keyBuilder.append(count[i]).append(",");
            }
            String key = keyBuilder.toString();

            // 将字符串插入哈希表
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }

        // 返回哈希表中所有的值
        return new ArrayList<>(map.values());
    }
}

复杂度分析

时间复杂度：
- 遍历所有字符串：O(N)，N 是数组长度。
- 统计字符频率：O(K)，K 是字符串平均长度。
- 总复杂度：O(N * K)。
空间复杂度：
- 哈希表存储结果，空间复杂度为 O(N * K)。

适用场景

当字符串较长时，字母计数的效率更高，可以替代排序操作。
非常适合后期优化和性能要求较高的场景。

解法 3：质数乘积映射（进阶解法）

解法描述

核心思想：将字符映射为质数，用乘积唯一标记异位词
- 因为不同质数的乘积是唯一的（数学性质），我们可以用每个字母对应一个质数，将一个字符串的乘积表示为一个数值。
- 如果两个字符串组成的质数乘积相同，则它们必然是字母异位词。
实现方式：
- 定义一个数组，将每个字母从 'a' 到 'z' 映射到第 i 个质数。
- 对每个字符串计算其映射值（用长整型避免溢出），用其作为哈希表的 key 进行分组。

代码模板

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 每个字母对应的质数值
        int[] primes = {
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
            53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101
        };

        Map<Long, List<String>> map = new HashMap<>();

        for (String s : strs) {
            long key = 1;
            for (char c : s.toCharArray()) {
                key *= primes[c - 'a'];
            }

            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }

        return new ArrayList<>(map.values());
    }
}