题目链接

题目描述

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

示例

示例1：

输入：[“bella”,”label”,”roller”] 输出：[“e”,”l”,”l”]

提示

  1. 1 <= A.length <= 100
  2. 1 <= A[i].length <= 100
  3. A[i][j] 是小写字母

    思路

    哈希表

    统计每个字符串里字符出现的频次，然后取每个字符的最小频次即可。

    题解

    1. class Solution {
    2. public:
    3.  vector<string> commonChars(vector<string>& words) {
    4.      vector<string> ans;
    5.      if (0 == words.size()) {
    6.          return ans;
    7.      }
    8.      int minCount[26] = {0};
    9.      int count[26] = {0};
    10.      for (int i = 0; i < 26; ++i) {
    11.          minCount[i] = INT_MAX;
    12.      }
    13.      for (string& word : words) {
    14.          memset(count, 0, 26 * sizeof(int));
    15.          for (char c : word) {
    16.              ++count[c - 'a'];
    17.          }
    18.          for (int i = 0; i < 26; ++i) {
    19.              minCount[i] = min(minCount[i], count[i]);
    20.          }
    21.      }
    22.      for (int i = 0; i < 26; ++i) {
    23.          for (int j = 0; j < minCount[i]; ++j) {
    24.              ans.emplace_back(1, i + 'a');
    25.          }
    26.      }
    27.      return ans;
    28.  }
    29. };

    复杂度分析

    1002-查找常用字符 - 图1 为字符集大小，本题为26，1002-查找常用字符 - 图2 为数组大小，1002-查找常用字符 - 图3 为字符串平均长度。
  • 时间复杂度：1002-查找常用字符 - 图4
  • 空间复杂度：1002-查找常用字符 - 图5