CTF of Z2BNS
0%

查找常用字符

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

示例1：

1
2
输入：["bella","label","roller"]
输出：["e","l","l"]

示例2：

1
2
输入：["cool","lock","cook"]
输出：["c","o"]

提示：

  1. 1 <= A.length <= 100
  2. 1 <= A[i].length <= 100
  3. A[i][j] 是小写字母
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

就是查找多个字符串中的交集（都有的字符），以一个字符串为主进行遍历，然后依次判断每个字符是否在其它字符串中存在，有则添加到结果中并在其它字符串中删除该字符（防止一个字符匹配多次），否则终止进行下一个字符判断。

c++代码：(执行用时8ms，击败96.77%，内存消耗9M，击败75.28%）

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
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        vector<string> result;
        //遍历数组A中的第一个元素中的字符（A.length()>=1），其实遍历A中长度最小的元素比较好
        for(char i:A[0]){
            //在其它元素中依次查找A[0]中的字符是否存在
            for(int j=1;j<A.size();++j){
                if(A[j].find(i)!=string::npos){
                    //删除找到的字符
                    A[j].erase(A[j].find(i),1);
                    if(j==A.size()-1){
                        //该字符在所有元素中都存在
                        //把字符i转成字符串
                        result.push_back(string(1,i));
                    }
                }else{
                    //若某个元素中没有这个字符则跳出循环，即该字符不满足要求
                    break;
                }
            }
        }
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：计数

思路与算法

根据题目的要求，如果字符 cc 在所有字符串中均出现了 $k$ 次及以上，那么最终答案中需要包含 $k$ 个 $c$。因此，我们可以使用 $\textit{minfreq}[c]$ 存储字符 $c$ 在所有字符串中出现次数的最小值。

我们可以依次遍历每一个字符串。当我们遍历到字符串 $s$ 时，我们使用 $\textit{freq}[c]$ 统计 ss 中每一个字符 $c$ 出现的次数。在统计完成之后，我们再将每一个 $\textit{minfreq}[c]$ 更新为其本身与 $\textit{freq}[c]$ 的较小值。这样一来，当我们遍历完所有字符串后，$\textit{minfreq}[c]$ 就存储了字符 $c$ 在所有字符串中出现次数的最小值。

由于题目保证了所有的字符均为小写字母，因此我们可以用长度为 $26$ 的数组分别表示 $\textit{minfreq}$ 以及 $\textit{freq}$。

在构造最终的答案时，我们遍历所有的小写字母 $c$，并将 $\textit{minfreq}[c]$个 $c$ 添加进答案数组即可。

c++代码：(执行用时12ms，击败76.58%，内存消耗9.1M，击败51.59%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        vector<int> minfreq(26, INT_MAX);
        vector<int> freq(26);
        for (const string& word: A) {
            fill(freq.begin(), freq.end(), 0);
            for (char ch: word) {
                ++freq[ch - 'a'];
            }
            for (int i = 0; i < 26; ++i) {
                minfreq[i] = min(minfreq[i], freq[i]);
            }
        }

        vector<string> ans;
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < minfreq[i]; ++j) {
                ans.emplace_back(1, i + 'a');
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：$O(n(m+|\Sigma|))$，其中 $n$ 是数组 $A$的长度（即字符串的数目），$m$是字符串的平均长度，$\Sigma$ 为字符集，在本题中字符集为所有小写字母，$|\Sigma|=26$。

遍历所有字符串并计算 $\textit{freq}$的时间复杂度为 $O(nm)$；
使用 $\textit{freq}$ 更新 $\textit{minfreq}$ 的时间复杂度为 $O(n|\Sigma|)$；
由于最终答案包含的字符个数不会超过最短的字符串长度，因此构造最终答案的时间复杂度为 $O(m+|\Sigma|)$。这一项在渐进意义上小于前二者，可以忽略。
空间复杂度：$O(|\Sigma|)$，这里只计算存储答案之外的空间。我们使用了数组 $\textit{freq}$freq 和 $\textit{minfreq}$，它们的长度均为 $|\Sigma|$。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

官方题解使用的又是计数法，遇到好多题都有计数法，我倒是没用过计数法🤣，还是比较喜欢用最直观的解法，效率也不错。

------------- THE END! THANKS! -------------