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] 由小写英文字母组成

解题思路

这道题要求找出在所有字符串中都出现的字符，需要考虑字符的重复次数。

思路分析：

  1. 哈希表统计法：对每个字符串统计字符频次，然后求所有字符串中每个字符频次的最小值

    • 用一个数组记录第一个字符串中每个字符的频次
    • 遍历后续字符串，更新每个字符的最小频次
    • 最后根据最小频次构造结果

  2. 集合交集法：将每个字符串转为字符集合（考虑重复），然后求交集

    • 时间复杂度较高，不推荐

推荐解法：哈希表统计法

  • 使用长度为26的数组统计字符频次（因为只有小写字母）
  • 第一个字符串建立基准频次，后续字符串更新最小频次
  • 最后根据最终频次生成结果数组

时间复杂度较优，空间使用简洁。

代码实现

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<int> count(26, INT_MAX);
        
        for (const string& word : words) {
            vector<int> temp(26, 0);
            for (char c : word) {
                temp[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                count[i] = min(count[i], temp[i]);
            }
        }
        
        vector<string> result;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < count[i]; j++) {
                result.push_back(string(1, 'a' + i));
            }
        }
        
        return result;
    }
};

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        from collections import Counter
        
        # 初始化为第一个单词的字符计数
        count = Counter(words[0])
        
        # 对后续每个单词，求交集的最小计数
        for word in words[1:]:
            word_count = Counter(word)
            for char in count:
                count[char] = min(count[char], word_count.get(char, 0))
        
        # 根据最终计数构造结果
        result = []
        for char, freq in count.items():
            result.extend([char] * freq)
        
        return result

public class Solution {
    public IList<string> CommonChars(string[] words) {
        int[] count = new int[26];
        Array.Fill(count, int.MaxValue);
        
        foreach (string word in words) {
            int[] temp = new int[26];
            foreach (char c in word) {
                temp[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                count[i] = Math.Min(count[i], temp[i]);
            }
        }
        
        List<string> result = new List<string>();
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < count[i]; j++) {
                result.Add(((char)('a' + i)).ToString());
            }
        }
        
        return result;
    }
}

var commonChars = function(words) {
    let count = new Array(26).fill(Infinity);
    
    for (let word of words) {
        let temp = new Array(26).fill(0);
        for (let char of word) {
            temp[char.charCodeAt(0) - 97]++;
        }
        for (let i = 0; i < 26; i++) {
            count[i] = Math.min(count[i], temp[i]);
        }
    }
    
    let result = [];
    for (let i = 0; i < 26; i++) {
        for (let j = 0; j < count[i]; j++) {
            result.push(String.fromCharCode(97 + i));
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × m)n是字符串数量，m是字符串平均长度
空间复杂度O(1)使用固定大小的数组(26)，不随输入规模变化

相关题目