[leetcode]916. Word Subsets

Analysis

今天被微博上的孙艺兴bot笑死，哈哈哈哈哈—— [每天刷题并不难0.0]

We are given two arrays A and B of words. Each word is a string of lowercase letters.
Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity. For example, “wrr” is a subset of “warrior”, but is not a subset of “world”.
Now say a word a from A is universal if for every b in B, b is a subset of a.
Return a list of all universal words in A. You can return the words in any order.

Explanation:
遍历A，如果A中的字符串a，如果B中的每个字符串都包含在a中，则把a保存下来~

Implement

class Solution {
public:
    vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
        vector<string> res;
        vector<int> cnt(26, 0);
        vector<int> tmp_cnt(26, 0);
        for(string b:B){
            tmp_cnt = helper(b);
            for(int i=0; i<26; i++)
                cnt[i] = max(cnt[i], tmp_cnt[i]);
        }
        int flag;
        for(string a:A){
            tmp_cnt = helper(a);
            flag = 1;
            for(int i=0; i<26; i++){
                if(cnt[i] > tmp_cnt[i]){
                    flag = 0;
                    break;
                }
            }
            if(flag)
                res.push_back(a);
        }
        return res;
    }
private:
    vector<int> helper(string& str){
        vector<int> cnt(26, 0);
        for(char c:str)
            cnt[c-'a']++;
        return cnt;
    }
};