LeetCode 1002. 查找共用字符

2026-04-09 HGNULB 约 5 分钟

文章信息 9 个分类 3 个标签

分类

题目描述

✅ 1002. 查找共用字符

题意分析

给一个字符串数组 words，要找出在每一个字符串里都出现过的字符，并按出现次数把它们列进答案。关键在后半句：如果某个字符在每个字符串中至少出现 k 次，那它就要在答案里出现 k 次。答案可以按任意顺序返回。

「重复的字符要重复列出」这一条把题目从集合运算变成了多重集合的交集。只判断「有没有」是不够的——["bella","label","roller"] 里字母 l 在三个词中分别出现 2、2、2 次，答案要有两个 l。而多重集交集的每个元素的重数，等于它在各个集合中重数的最小值，这就是整道题的全部数学内容。

约束里写明所有字符串只含小写字母，这是最强的信号：字符集大小固定为 26，可以用长度 26 的定长数组代替哈希表，索引直接由 c - 'a' 算出，常数极小且不需要处理哈希冲突。凡是「只含小写字母」的题都该条件反射地想到这一点。

数据规模上，字符串数量与单串长度都不大，总字符数是线性可扫的，所以不需要任何高级技巧，只要保证不做重复的两两比较即可。

边界要盯住：words 只有一个字符串时，答案就是这个字符串的全部字符（按重数）；某个字符串完全不含某字母时，该字母的最小次数为 0，必须被排除；答案可能为空数组。

解法：逐位维护最小词频

核心思路

答案要求保留重复字符，本质是多个字符串的多重集交集。某个字母能出现多少次，取决于它在所有单词中的最少出现次数。

字符只可能是 a 到 z，用长度 26 的数组 minFreq 维护全局最小词频。对每个单词单独计数，再逐位取最小值。处理完前若干个单词后，不变量是：minFreq[c] 等于字母 c 在这些单词中的最少出现次数。

最后按 a 到 z 遍历，每个字母加入答案 minFreq 次。题目不要求输出顺序，这个顺序稳定且无需额外排序。

解题步骤

将 minFreq 的 26 个位置初始化为足够大的值。

对每个单词建立独立的 freq 数组并统计字符次数。

遍历 26 个字母，用 minFreq[i] = min(minFreq[i], freq[i]) 合并当前单词。

按最终最小词频重建字符串列表。

例如 ["bella","label","roller"] 中，e 的最小次数为 1，l 的最小次数为 2，其余字母为 0，所以答案是 ["e","l","l"]。

代码实现

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

class Solution {
    public List<String> commonChars(String[] words) {
        int[] minFreq = new int[26];
        Arrays.fill(minFreq, Integer.MAX_VALUE);

        for (String word : words) {
            int[] freq = new int[26];
            for (int i = 0; i < word.length(); i++) {
                freq[word.charAt(i) - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                minFreq[i] = Math.min(minFreq[i], freq[i]);
            }
        }

        List<String> answer = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            for (int count = 0; count < minFreq[i]; count++) {
                answer.add(String.valueOf((char) ('a' + i)));
            }
        }
        return answer;
    }
}

func commonChars(words []string) []string {
    minFreq := [26]int{}
    for i := range minFreq {
        minFreq[i] = int(^uint(0) >> 1)
    }

    for _, word := range words {
        freq := [26]int{}
        for i := 0; i < len(word); i++ {
            freq[word[i]-'a']++
        }
        for i := 0; i < 26; i++ {
            if freq[i] < minFreq[i] {
                minFreq[i] = freq[i]
            }
        }
    }

    answer := []string{}
    for i, count := range minFreq {
        for ; count > 0; count-- {
            answer = append(answer, string(byte('a'+i)))
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(S)$，其中 $S$ 是所有字符串的总长度；每个单词额外扫描固定的 26 个桶。

空间复杂度：不计返回值为 $O(1)$，只使用两个长度固定的计数数组。

关键点总结

共用字符带重数，必须求多重集交集，不能只记录是否出现。

多重集交集中某元素的次数等于各集合中次数的最小值。

小写字母值域固定，数组比哈希表更直接，也自然按字母序输出。

每个单词的临时词频必须重新清零，再与全局最小值合并。

易错点总结

忽略重复次数：示例中会少返回一个 l。

把 minFreq 初始化为 0：逐位取最小后永远都是 0。

复用却不清空临时计数数组：词频会跨单词累加，交集被放大。

只更新当前单词出现过的字母：没出现意味着次数为 0，也必须把全局最小值降为 0。

逐位取最大值：得到的是并集式计数，而不是所有单词都拥有的字符。

相似题目

题目	难度	考察点
350. 两个数组的交集 II	简单	同为多重集交集但只有两个数组且值域不限，需用哈希表计数或双指针配合排序
349. 两个数组的交集	简单	结果需去重，退化成普通集合交集，正好对照本题为何必须保留重数
383. 赎金信	简单	判断一个词频是否被另一个覆盖，只需比较大小而不必求最小值
242. 有效的字母异位词	简单	要求两个词频完全相等，同样用 26 长度数组，可加减一次遍历完成
438. 找到字符串中所有字母异位词	中等	词频比较搬到滑动窗口里，需要增量更新并维护「已匹配字母数」
1160. 拼写单词	简单	逐个单词与字母表词频比对并累加长度，是本题「逐位比较」的另一种聚合方式
387. 字符串中的第一个唯一字符	简单	同样用 26 长度计数数组，但关注的是次数为 1 且需要回到原串求最小下标
451. 根据字符出现频率排序	中等	统计之后按频次排序输出，重点从「求交」转为「按计数重建字符串」