leetcode916 单词子集

题目

单词子集

分析

根据题意，题目中给出了两个集合A和B，B中的单词为b，B中的每个b都是A中某个a的子集，那么a就叫通用单词。

例子1：a = "abc" B = {"a", "b"}，"a"和"b"都是"abc"的子集，那么a是通用单词。
例子2：a = "abc" B = {"aa", "b"}，"aa"不是"abc"的子集，那么a不是通用单词。

通过上述例子我们可以发现，a至少要包含B中每个字母出现的最小次数，a才能是通用单词。

所以解法很简单，求一遍B中每个字母出现的最小次数，然后再遍历A中每个单词做判断即可。

代码

class Solution {
private:
    vector<int> get_vec(string& s) {
        vector<int> res(26, 0);
        for (auto & c : s) {
            res[c - 'a']++;
        }
        return res;
    }

    void merge_vec(vector<int>& A, vector<int>& B) {
        for (int i = 0; i < 26; i++) {
            A[i] = (B[i] > A[i]) ? B[i] : A[i]; 
        }
    }

    bool check(vector<int>& A, vector<int>& B) {
        for (int i = 0; i < 26; i++) {
            if (B[i] > A[i]) {
                return false;
            }
        }
        return true;
    }
public:
    vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
        vector<int> num_B(26, 0);
        for (auto & str : B) {
            vector<int> vec(get_vec(str));
            merge_vec(num_B, vec);
        }

        vector<string> res;
        for (auto & str : A) {
            vector<int> vec(get_vec(str));
            if (check(vec, num_B)) {
                res.push_back(str);
            }
        }

        return res;
    }
};