LeetCode 1002. 查找共用字符
题目描述
题意分析
返回每个单词都拥有的字符，并保留能够共同提供的重复份数。字符不要求连续，也不要求在单词中处于相同位置，答案顺序任意。
因为输入只包含小写英文字母，可以分别统计 26 个字母的出现次数。问题不是普通集合交集，而是每种字符最多能取多少份的多重集合交集。
解法：逐位维护最小词频
核心思路
[!blue]
对某个字符，设它在各个单词中的出现次数分别为若干个频次。共同答案中的份数不能超过任意一个单词的频次，所以最多只能取这些频次的最小值；反过来，每个单词都至少拥有这么多份，因此取这个最小值一定可行。不同字符之间没有顺序限制，可以独立计算。
用
freq[c]记录当前单词中字母c的次数，用minFreq[c]记录已经处理的所有单词中该字母的最小次数。每读完一个单词，就对全部 26 个位置执行minFreq[c] = min(minFreq[c], freq[c])。这样处理完前几个单词后，minFreq始终就是它们的共同字符频次。
minFreq先填最大整数，第一次取最小时就会被首个单词的真实频次替换。题目保证至少有一个单词，因此初值不会残留到输出阶段。每个单词都重新建立清零的freq，没有出现的字母频次为0，也必须参与比较；只要某个单词缺少这个字母，它就不能出现在共同答案中。最后逐个字母读取
minFreq，把对应的单字符字符串重复加入答案。按字母顺序生成只是一种方便的输出方式，符合答案顺序任意的要求。
解题步骤
- 建立长度为
26的minFreq，全部初始化为最大整数。- 对每个单词建立新的零频次表
freq，扫描字符并用字符 - 'a'定位计数位置。- 遍历所有 26 个位置，用当前词频更新
minFreq的逐项最小值，包括频次为0的位置。- 所有单词处理完后，将字母
c对应的字符串加入答案minFreq[c]次。次数为0的字母不输出。
代码实现
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
}
复杂度分析
设单词数为
m，全部单词的字符总数为S，答案包含R个字符。
- 时间复杂度：$O(S + 26m + R)$。统计扫描全部字符，每个单词合并 26 项，再输出
R项。由于每个单词非空、字母表固定，且答案不长于最短单词，可以简化为 $O(S)$。- 空间复杂度：$O(1)$ 辅助空间，只保存两个长度为 26 的频次表；返回结果另占 $O(R)$。
关键点总结
[!green]
- 某个字母的共同份数等于它在所有单词中的最小频次，既不能更多，也一定能取到这么多。
- 临时频次表只描述一个单词，全局频次表描述已处理单词的交集。
- 缺失字母的零频次决定该字母不能保留，必须参与合并。
- 输出每个字符的全部共同份数，不能用普通集合去重。
易错点总结
[!yellow]
- 将
minFreq初始化为0再取最小值，会使所有结果永远停留在0。- 不清空每个单词的临时频次，会把多个单词的出现次数累加，失去单词之间取交集的含义。
- 只更新当前单词出现过的字母，会忽略缺失字符对应的零，使答案保留不共用的字符。
- 每个字母只输出一次，会丢失重复份数；需要按最终最小频次重复输出。
- 逐位置比较字符或寻找共同子串，会错误地附加题目没有要求的位置和顺序限制。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 350. 两个数组的交集 II | 简单 | 把两组多重集合交集推广到多个单词，对每个字符取所有词中出现次数的最小值。 |
| 383. 赎金信 | 简单 | 同样按字符需求次数处理重复，本题找所有来源共同能提供的字符，而不是验证一个固定目标。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！