查找共用字符

难度: Easy

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

示例 1：

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

示例 2：

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

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 由小写英文字母组成

Submission

运行时间: 30 ms

内存: 16.1 MB

class Solution:
    def commonChars(self, words: list[str]) -> list[str]:
        res=[]
        w_c=set(words[0])
        for w in w_c:
            num_list=[]
            for wd in words:
                num_list.append(wd.count(w))
            small=min(num_list)
            res.extend(small*w)
        return res

Explain

此题解使用集合和列表来找出所有字符串共有的字符。首先，取出第一个单词的所有不同字符形成一个集合。对于这个集合中的每个字符，遍历输入的所有单词，计算每个单词中该字符出现的次数。然后，取这些次数中的最小值，表示该字符在所有单词中共同出现的最少次数。接着，将这个字符重复最小次数次，添加到结果列表中。这样做能确保仅包含所有单词都至少有的字符，并正确处理重复字符的情况。

时间复杂度: O(K*N*M)

空间复杂度: O(M)

class Solution:
    def commonChars(self, words: list[str]) -> list[str]:
        res = []  # 结果列表
        w_c = set(words[0])  # 从第一个单词中获取所有不同的字符
        for w in w_c:  # 遍历每个字符
            num_list = []  # 存储每个单词中该字符的出现次数
            for wd in words:  # 遍历每个单词
                num_list.append(wd.count(w))  # 计算并添加该字符的出现次数
            small = min(num_list)  # 找到该字符在所有单词中的最小出现次数
            res.extend(small * w)  # 将字符重复最小次数次，添加到结果列表
        return res  # 返回结果列表

Explore

从第一个单词构建字符集合是为了简化实现和减少一开始的计算量。如果从所有单词的共同集合开始，需要先做一次遍历所有单词以找出共有字符，这会增加算法的复杂度。选择第一个单词作为起始点，是因为无论选哪个单词作为起始，最终的结果都是相同的，因此从第一个单词开始计算是一种方便且常见的做法。

使用count函数确实会导致每次计算字符出现次数时重复遍历单词，这样在多单词和长单词的情况下效率较低。更高效的方法是在遍历每个单词时，直接构建一个字典来记录每个字符的出现次数，这样只需遍历每个单词一次。之后对于每个字符，只需要查字典中的值，而不是重复调用count函数。

如果输入中的任何一个单词是空字符串，那么算法的结果将是空列表，因为空字符串不包含任何字符，即没有任何字符会在所有单词中都出现。在实际应用中，可能需要提前检查输入并处理空字符串的情况，例如通过预处理步骤排除空字符串，以避免无谓的计算。

解法中使用set是为了快速检查和去除重复字符，使用list是为了存储最终的结果和中间的字符出现次数。考虑到字典（dict）的高效键值对映射特性，可以用字典来优化字符计数的过程。使用字典而不是多次调用count函数，可以减少重复的字符串遍历，提高整体效率。