🏞 1002.查找共用元素
给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。
示例
示例 1：
1
2
| 输入：words = ["bella","label","roller"]
输出：["e","l","l"]
|
示例 2：
1
2
| 输入：words = ["cool","lock","cook"]
输出：["c","o"]
|
思路
基本思想
为了找到words中每个单词都出现的字符，需要现将每个单词中的字符出现次数统计出来，最开始的想法是既然查找的是共用字符，那么字符出现的次数至少是words的长度，所以只需要在统计每个单词中字符出现次数时，字符首次出现时才需要统计，最终看哪个字符出现的次数与words的长度相等，但是这样不符合示例1
示例1给出的答案包含两个l，也就是说一个字符在公共字符中可以重复出现，只要他在每个单词中出现的次数都不止一次即可
所以需要更换思路，公共字符出现的次数肯定是所有单词中出现次数最少的，也就是示例2中，第一个单词中o出现两次，第二个单词中o出现一次，第三个单词中o出现两次，最终的结果o只能出现一次
所以以此为突破口，统计出每个单词中字符的出现次数之后，需要与下一个单词进行比较，留下最小的出现次数，遍历结束之后，出现次数不为零的字符就是共用字符
统计出来之后，留下最小值
执行流程
- 遍历words中的所有单词
- 对于每一个单词统计字符出现的次数
- 保留当前每个字符出现的最小次数
- words遍历结束之后，统计字符出现的次数，字符出现次数不为零，说明其是公共字符
- 出现次数是几，就需要将其加入到结果容器中几次
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
//有可能某一个字符在words中的每一个单词中都不止出现一次
//所以统计每个单词中字母出现的次数，在个单词中，取每个字符出现次数的最小值
//遍历完成之后，所有大于零位置的字符，出现几次就是公共字符是几个
vector<string> commonChars(vector<string>& words) {
vector<int> minCount(26,INT_MAX);
//遍历每一个单词
for(int i=0;i<words.size();++i){
vector<int> temp(26,0);
//统计每一个单词出现的次数
for(int j=0;j<words[i].size();++j){
temp[words[i][j]-'a']+=1;
}
//取当前字符出现的最小值，也就是公共部分
for(int j=0;j<temp.size();++j){
minCount[j]=min(minCount[j],temp[j]);
}
}
//minCount中保存的就是公共部分，字符出现几次说明公共部分就是多大
vector<string> res;
for(int i=0;i<minCount.size();++i){
//对应字符出现几次就添加几个字符
for(int j=0;j<minCount[i];++j){
res.emplace_back(1, i + 'a');
//等同于下面两句，直接在原地新建一个字符串并添加到末尾
// string s(1,i+'a');
// res.push_back(s)
}
}
return res;
}
};
|
总结
要清楚最终的共用字符就是所有单词中的公共部分，出现的次数肯定是最小的，所以可以在统计单词中字符出现次数的时候把对应字符的最小出现次数记录下来，遍历结束之后，按照字符出现的次数来统计最终的结果
