LeetCode LCR 033. 字母异位词分组

Categories:

题目描述
思路分析
1. 解法一：排序作哈希键（推荐）
2. 解法二：字符频次数组作哈希键
相似题目

题目描述

✅ LCR 033. 字母异位词分组

思路分析

解法一：排序作哈希键（推荐）

核心思路：

字母异位词的特征：包含完全相同的字母，只是顺序不同。

对每个单词的字母排序后，所有异位词会得到相同的字符串，可作为哈希表的分组键。

遍历所有单词，将每个单词归入以排序结果为键的分组，最后返回所有分组。

复杂度分析：

时间复杂度：O(nk log k)，其中 n 为单词数，k 为最长单词的长度，每个单词排序需 O(k log k)

空间复杂度：O(nk)，哈希表存储所有单词

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);
            // 将原单词追加到对应分组
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

func groupAnagrams(strs []string) [][]string {
    mp := map[string][]string{}
    for _, s := range strs {
        // 对字节切片排序，得到分组键
        b := []byte(s)
        sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
        key := string(b)
        mp[key] = append(mp[key], s)
    }
    res := make([][]string, 0, len(mp))
    for _, v := range mp {
        res = append(res, v)
    }
    return res
}

解法二：字符频次数组作哈希键

核心思路：

用长度为 26 的计数数组统计每个单词中各字母出现的次数。

将计数数组序列化为字符串（如 "1#0#0#..."）作为哈希键，避免排序开销。

所有异位词的字符频次完全相同，因此映射到同一键，实现分组。

复杂度分析：

时间复杂度：O(nk)，其中 n 为单词数，k 为最长单词的长度，统计字符频次只需 O(k)

空间复杂度：O(nk)，哈希表存储所有单词

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            // 统计 26 个字母的出现次数
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            // 将频次数组序列化为字符串键，用 '#' 分隔避免歧义
            StringBuilder sb = new StringBuilder();
            for (int n : count) {
                sb.append(n).append('#');
            }
            String key = sb.toString();
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

func groupAnagrams(strs []string) [][]string {
    mp := map[[26]int][]string{}
    for _, s := range strs {
        // 统计 26 个字母的出现次数
        var count [26]int
        for _, c := range s {
            count[c-'a']++
        }
        // 直接用数组作为 map 的键（Go 中数组是值类型，可比较）
        mp[count] = append(mp[count], s)
    }
    res := make([][]string, 0, len(mp))
    for _, v := range mp {
        res = append(res, v)
    }
    return res
}

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	哈希表、字符频次
438. 找到字符串中所有字母异位词	中等	滑动窗口、字符频次
567. 字符串的排列	中等	滑动窗口 + 频次比较
1002. 查找共用字符	简单	哈希表、字符频次
266. 回文排列	简单	哈希表、字符频次奇偶性
383. 赎金信	简单	哈希表、字符频次
1347. 制造字母异位词的最小步骤数	中等	哈希表、字符频次差值

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/91362306