1002.Find Common Characters

Tags: Array Hash Table Easy

Links: https://leetcode.com/problems/find-common-characters/

---

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

Note:

1. 1 <= A.length <= 100
2. 1 <= A[i].length <= 100
3. A[i][j] is a lowercase letter

---

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        vector<int> cnt(26, INT_MAX);
        vector<string> res;
        for (auto& s : A) 
        {
            vector<int> tmp(26, 0);
            for (auto c : s) ++tmp[c - 'a'];
            for (int i = 0; i < 26; ++i) cnt[i] = min(cnt[i], tmp[i]);
        }

        for (int i = 0; i < 26; ++i)
        {
            for (int j = 0; j < cnt[i]; ++j) res.push_back(string(1, i + 'a'));
        }

        return res;
    }
};

对于每个单词，统计各个字母在这个单词出现的次数，总体取最小值，加入到结果数组即可。