问题解构与核心逻辑
给定一个字符串数组 words，要求返回一个列表，其中包含在所有字符串中都出现的字符。字符区分大小写，题目说明中均为小写字母。关键约束如下：
例如，输入 words = ["bella","label","roller"]，字符 ‘l’ 在三个字符串中分别出现2、2、2次，因此结果中加入两个 "l"；字符 ‘e’ 分别出现1、1、1次，结果中加入一个 "e"。输出为 ["e","l","l"]。
C++解法：数组计数法
由于字符限定为小写字母，可以使用长度为26的整型数组作为哈希表来统计字符频率，这是最高效的方法。
算法步骤
- 对每个字符串 word，创建一个临时数组 charCount(26, 0) 统计其字符频率。
- 遍历 word 中的每个字符，对应 charCount 索引（c – 'a'）加1。
- 遍历26个字母，将 minFreq 的每个位置更新为 min(minFreq[i], charCount[i])。
C++代码实现
#include <vector>
#include <string>
#include <algorithm>
#include <climits> // 用于INT_MAX
using namespace std;
class Solution {
public:
vector<string> commonChars(vector<string>& words) {
// 步骤1：初始化最小频率数组
vector<int> minFreq(26, INT_MAX);
// 步骤2：遍历所有单词，更新最小频率
for (const string& word : words) {
vector<int> charCount(26, 0);
// 统计当前单词的字符频率
for (char c : word) {
charCount[c – 'a']++;
}
// 更新全局最小频率
for (int i = 0; i < 26; ++i) {
minFreq[i] = min(minFreq[i], charCount[i]);
}
}
// 步骤3：根据最小频率构建结果
vector<string> result;
for (int i = 0; i < 26; ++i) {
// 将字符 (char)('a' + i) 重复 minFreq[i] 次加入结果
for (int j = 0; j < minFreq[i]; ++j) {
// 使用 emplace_back 直接在容器末尾构造字符串，效率优于 push_back
result.emplace_back(1, 'a' + i);
}
}
return result;
}
};
代码关键点解析：
- minFreq 初始化为 INT_MAX：确保第一次与 charCount 取 min 时，能正确更新为 charCount 的值。
- 内层循环 for (char c : word)：遍历字符串的简便写法。
- c – 'a'：将字符 ‘a’-‘z‘ 映射到数组索引 0-25 的标准方法。
- result.emplace_back(1, 'a' + i)：这是构建结果的关键。emplace_back 直接在 result 向量的末尾构造一个字符串对象，该字符串由1个字符 (‘a’ + i) 组成。这比先创建临时字符串再用 push_back 更高效。
复杂度分析
- 时间复杂度：O(N * M)，其中 N 是数组 words 的长度，M 是数组中字符串的平均长度。我们需要遍历每个字符串的每个字符两次（一次统计，一次更新最小值），但常数项可以忽略，仍为线性复杂度。
- 空间复杂度：O(1) 或 O(∣Σ∣)，其中 ∣Σ∣ 是字符集大小（此处为26）。我们只使用了固定大小的辅助数组，与输入数据规模无关。
与其他解法的对比
为了更全面理解，下表将本解法与另一种常见的哈希表（unordered_map）解法进行对比：
| 数据结构 | 固定大小的 vector<int>（大小26） | unordered_map<char, int> |
| 适用场景 | 字符集已知且较小（如小写字母） | 字符集未知或较大（如Unicode） |
| 时间复杂度 | O(N * M)，访问数组为O(1) | O(N * M)，哈希表操作平均O(1) |
| 空间复杂度 | O(1) | O(∣Σ∣)，但常数开销更大 |
| 性能 | 更优。内存连续，CPU缓存友好，无哈希冲突开销。 | 稍差。涉及哈希计算和动态内存管理。 |
| 代码简洁性 | 简单直观 | 相对复杂，需要处理键不存在的情况 |
对于本题（仅小写字母），数组计数法是绝对最优选择，其效率远高于哈希表法。
关联题目与模式总结
此题的本质是求多个集合（每个字符串的字符频次）的交集，且交集中元素的重数取其在各集合中出现次数的最小值。这种“计数取最小”的模式可以推广到一系列问题：
| 1002. 查找常用字符 | 求多个字符串的字符频率最小交集 | 本题本身 |
| 349. 两个数组的交集 | 求两个数组的唯一公共元素集合 | 简化版，只求是否存在，不统计次数 |
| 350. 两个数组的交集 II | 求两个数组的公共元素，并保留最小出现次数 | 可以看作本题在两个“字符串”（数组）上的特例 |
| 242. 有效的字母异位词 | 比较两个字符串的字符频率是否完全相同 | 使用相同的数组计数技术 |
掌握这种基于固定数组的频次统计与比较方法，是解决许多字符串处理与哈希类问题的基础技能。
参考来源
- 1002. Find Common Characters*
- leetcode 1002. 查找常用字符
- leetcode-1002：查找常用字符
- LeetCode第349题_两个数组的交集
- LeetCode第313题_超级丑数
- Leetcode 1002：查找常用字符
