1002. 查找常用字符

给定仅有小写字母组成的字符串数组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]$是小写字母

思路

方法一：计数

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

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

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

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

code

class Solution:
    def commonChars(self, A: List[str]) -> List[str]:
        minfreq = [float("inf")] * 26
        # print(minfreq)
        for word in A:
            freq = [0] * 26
            for ch in word:
                freq[ord(ch) - ord("a")] += 1
            for i in range(26):
                minfreq[i] = min(minfreq[i], freq[i])
                # print(minfreq[i])
        ans = []
        for i in range(26):
            if minfreq:
                ans.extend([chr(ord("a")+ i)] * minfreq[i])
        return ans

复杂度分析

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

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