[Leetcode 1002] 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 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] is a lowercase letter

解题思路

用哈希表ansMap记录当前可能字符以及其出现次数，也就是把字符作为key，频率作为value
用哈希表midMap记录当前字符串的字符以及出现次数，同样把字符作为key，频率作为value

核心思想:

用第一个字符串初始化ansMap
遍历剩余字符串，每次遍历前，先清空midMap，再遍历当前字符串，更新midMap；
将ansMap中的key与midMap做比较：
- 如果不在midMap中，直接在ansMap中删除这个key；
- 否则更新ansMap中key对应的value，取为midMap和ansMap中值较小的那个
遍历ansMap，确定返回的vector<string>

示例代码 (cpp)

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        if (A.size() == 0)
            return vector<string>();
        unordered_map<char, int> ansMap;
        unordered_map<char, int> midMap;
        vector<string> ans;
        for(auto c : A[0]) {
            ansMap[c]++;
        }
        for (auto i = 1; i < A.size() ; ++i) {
            midMap.clear();
            for (auto c : A[i]) {
                midMap[c]++;
            }
            if (ansMap.size() == 0) {
                return ans;
            }
            for (auto iter = ansMap.begin(); iter != ansMap.end(); ) {
                if (midMap.count(iter->first)) { 
                    ansMap[iter->first] = min(ansMap[iter->first], midMap[iter->first]);
                    iter++;
                }
                else {
                    iter = ansMap.erase(iter);
                }
            }
        }
        for (auto iter = ansMap.begin(); iter != ansMap.end(); iter++) {
            for (auto i = 0; i < ansMap[iter->first]; ++i) {
                ans.push_back(string(1, iter->first));
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: O(n)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！