哈希算法题目：查找共用字符

题目描述

给你一个字符串数组 words（长度在 1 到 100 之间），其中每个字符串仅由小写英文字母组成。你需要返回一个字符串列表，包含在所有字符串中都出现过的字符（包括重复字符，重复次数取决于该字符在所有字符串中出现的最小次数）。返回的列表可以按任意顺序排列。

示例

• 输入：words = ["bella","label","roller"]
• 输出：["e","l","l"]
  解释：
  字符 'l' 在每个单词中出现至少 2 次，'e' 在每个单词中至少出现 1 次。其他字符（如 'b'）并非在所有单词中都出现。

解题思路

我们可以分三步思考：

1. 问题本质：对于每个小写字母（共 26 个），找出它在所有单词中出现的最小次数。
2. 单个单词统计：对每个单词，计算其中每个字母的出现次数。
3. 合并结果：将所有单词的统计结果合并，取每个字母在所有单词中最小出现次数，输出对应次数的该字母。

解题步骤详解

第一步：建立基准字母计数

• 小写字母只有 26 个，我们可以创建一个长度为 26 的数组 minFreq，初始值设为一个大数（比如无穷大或第一个单词的字母计数）。
• minFreq[i] 表示在所有单词中，字母 (char)('a' + i) 出现的最小次数。

第二步：遍历每个单词统计字母频率

• 对于每个单词 word，创建一个长度为 26 的数组 freq，统计当前单词中每个字母的出现次数。
• 遍历单词的每个字符，将对应字母计数加一。
• 得到 freq 后，与 minFreq 进行比较：对每个字母 i，更新 minFreq[i] = min(minFreq[i], freq[i])。

第三步：根据最小频率生成结果

• 遍历 26 个字母，若 minFreq[i] > 0，说明该字母在所有单词中都出现过至少一次，且 minFreq[i] 是它在所有单词中出现的最小次数。
• 将字母 (char)('a' + i) 重复 minFreq[i] 次加入结果列表。

具体例子解析

以 words = ["bella","label","roller"] 为例：

1. 初始化 minFreq = [∞, ∞, …, ∞]（或用第一个单词统计初始化，这里我们先看过程）。
2. 处理第一个单词 "bella"：
   • 统计字母频率：b:1, e:1, l:2, a:1（其他为 0）。
   • 因为是第一个单词，minFreq 直接设为该频率数组。
3. 处理第二个单词 "label"：
   • 统计频率：l:2, a:1, b:1, e:1。
   • 比较并更新 minFreq：
     • minFreq['b'] = min(1, 1) = 1
     • minFreq['e'] = min(1, 1) = 1
     • minFreq['l'] = min(2, 2) = 2
     • minFreq['a'] = min(1, 1) = 1
     • 其余字母最小次数为 0。
4. 处理第三个单词 "roller"：
   • 统计频率：r:2, o:1, l:2, e:1。
   • 比较更新：
     • minFreq['b'] = min(1, 0) = 0（因为 "roller" 中没有 'b'）
     • minFreq['e'] = min(1, 1) = 1
     • minFreq['l'] = min(2, 2) = 2
     • minFreq['a'] = min(1, 0) = 0
     • minFreq['r'] = min(0, 2) = 0（因为前两个单词中没有 'r'）
5. 最终 minFreq 中：
   • 'e' 对应值 1
   • 'l' 对应值 2
   • 其余字母为 0
6. 输出：'e' 出现 1 次，'l' 出现 2 次 → ["e","l","l"]。

代码实现（Java）

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

public class Solution {
    public List<String> commonChars(String[] words) {
        // 初始化最小频率数组，设为最大值
        int[] minFreq = new int[26];
        for (int i = 0; i < 26; i++) {
            minFreq[i] = Integer.MAX_VALUE;
        }
        
        // 遍历每个单词
        for (String word : words) {
            int[] freq = new int[26];
            // 统计当前单词的字母频率
            for (char c : word.toCharArray()) {
                freq[c - 'a']++;
            }
            // 更新全局最小频率
            for (int i = 0; i < 26; i++) {
                minFreq[i] = Math.min(minFreq[i], freq[i]);
            }
        }
        
        // 生成结果
        List<String> result = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            while (minFreq[i] > 0) {
                result.add(String.valueOf((char)('a' + i)));
                minFreq[i]--;
            }
        }
        return result;
    }
}

时间复杂度分析

• 设单词个数为 n，单词平均长度为 m。
• 每个单词遍历一次统计频率，复杂度 O(n × m)。
• 每次更新 minFreq 需要 O(26) 常数时间。
• 总时间复杂度 O(n × m)，空间复杂度 O(26) = O(1)。

为什么这是哈希思想？

• 核心是将字母映射到固定长度的数组（一个简单的哈希表，键为字母，值为计数）。
• 通过对每个单词的哈希表求交集（取最小值），得到所有单词的公共字符计数。
• 虽然题目看似简单，但体现了哈希表在频率统计与集合交集中的典型应用。