1002. 查找常用字符-Easy.md

Description

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

Solution

1. 简单粗暴

• 对数组中每相邻两个字符取交集，并用交集结果更新数组

class Solution:
    def commonChars(self, A: List[str]) -> List[str]:
        def compare(s1, s2):
            res = ""
            for i in s1:
                if i in s2:
                    res += i
                    s2 = s2.replace(i, '', 1)
            return res
        
        if len(A) == 0:
            return []
        elif len(A) == 1:
            return [i for i in A[0]]
        else:
            for i in range(len(A)-1):
                res = compare(A[i], A[i+1])
                A[i+1] = res
            return [i for i in A[-1]]

2. 题解解法

• 维护一个hashmap，key为26个字母，value为该字母出现的次数
• 遍历数组A，hashmap更新每个字母出现次数的最小值，即min(hashmap[letter], count_in_A)
• 但该方法实际提交的时间开销比本人的笨方法高

class Solution:
    def commonChars(self, A: List[str]) -> List[str]:
        # 初始化列表，记录字符出现最少次数的部分
        min_freq = [0] * 26

        # 先记录第一个字符串的字符出现次数
        for ch in A[0]:
            min_freq[ord(ch)-ord('a')] += 1
        
        # 遍历后续，统计并比较取字符出现次数较小的情况
        for i in range(1, len(A)):
            other_freq = [0] * 26
            for ch in A[i]:
                other_freq[ord(ch)-ord('a')] += 1
            # 与 min_freq 中字符出现次数比对
            for j in range(26):
                min_freq[j] = min(min_freq[j], other_freq[j])
        
        ans = []
        # 将 min_freq 对应次数的输出字符
        for i in range(len(min_freq)):
            for _ in range(min_freq[i]):
                ans.append(chr(i+ord('a')))
        
        return ans