1002. 查找常用字符

一、题目

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

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

示例 1：

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

示例 2：

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

提示：

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

二、思路

1. 暴力法

这道题实际上就是统计列表A中所有字符串元素的共有部分。

所以下边就任选一个字符串元素作为基础（这里选择一个长度最短的字符串最合适），下边选择的是最后一个元素。统计这个字符串中所有字母出现的次数，以字母为键，次数为值，保存在一个字典d中。

然后对d中的键进行遍历，每遍历一个键key，然后就对列表A中的每一个剩余字符串中所有字母进行判断，如果键key在遍历到的这个字符串中存在，那么则对key在字符串中出现的次数与key对应的值进行比较，保留最小的那个，并重新赋值给key；不存在，则抛弃键key，开始对下一个键进行判断。

如此一来，我们便完成了字母的过滤以及统计。

三、代码

1. 暴力法

from collections import Counter
class Solution:
    def commonChars(self, A: List[str]) -> List[str]:
        d = dict(Counter(A.pop()))
        res = []
        # 保存d中不合适的字母
        not_in = set()
        for key in d.keys():
            for s in A:
                cur = Counter(s)
                if cur.get(key):
                    d[key] = d[key] if d[key] <= cur[key] else cur[key]
                else:
                    not_in.add(key)
                    break
        for key, count in d.items():
            if key not in not_in:
                res.extend([key]*count)
        return res

四、表现

method	运行时间	表现	内存消耗	表现
1. 暴力法	144ms	5.11%	13.5MB	6.58%