🔗 🟢 1002. Find Common Characters 1280

tags: `Weekly Contest 126` `計數(Counting)` `雜湊表(Hash Table)` `字串(String)`

題意

給定一個字串陣列 $words$ ，返回一個字元陣列，其中包含所有在 $words$ 中每個字串中都出現的字元（ 包括重複字元）。答案可以以任何順序返回。

思路：計數(Counting)

為了解決這個問題，我們可以採用計數(Counting) 的方法。首先，我們使用雜湊表或長度為 $26$ 的陣列來計算出在第一個字串中每個字元出現的次數，然後遍歷每個字串，更新每個字元在所有字串中出現的最小次數。最後，我們根據這些最小次數來構建結果。

具體步驟如下：

初始化 $cnt$ ，計算第一個字串中每個字元的出現次數。
遍歷後續的每個字串，更新每個字元的最小出現次數。
根據最小出現次數構建結果。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot (m + |\Sigma|))$ ，其中 $n$ 表示字串陣列 $words$ 的長度， $m$ 表示字串中的最大長度， $|\Sigma|$ 表示字元集合的大小，本題中 $|\Sigma| = 26$ 。
空間複雜度： $\mathcal{O}(|\Sigma|)$ 。

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        cnt = Counter(words[0])
        for word in words:
            cnt &= Counter(word)
        return [ch for ch, v in cnt.items() for _ in range(v)]

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<int> cnt(26, INT_MAX), cur(26, 0);
        for (auto &word : words) {
            fill(cur.begin(), cur.end(), 0);
            for (auto &ch : word) cur[ch - 'a']++;
            for (int i = 0; i < 26; i++) cnt[i] = min(cnt[i], cur[i]);
        }
        vector<string> ans, tmp;
        for (int i = 0; i < 26; i++) {
            tmp.resize(cnt[i]);
            fill(tmp.begin(), tmp.end(), string(1, i + 'a'));
            ans.insert(ans.end(), tmp.begin(), tmp.end());
        }
        return ans;
    }
};