1178. Number of Valid Words for Each Puzzle --- H !!!!!!!!~~~~

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

• word contains the first letter of puzzle.
• For each letter in word, that letter is in puzzle.
  For example, if the puzzle is "abcdefg", then valid words are "faced", "cabbage", and "baggage"; while invalid words are "beefed" (doesn't include "a") and "based" (includes "s" which isn't in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

 

Example :

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

 

Constraints:

• 1 <= words.length <= 10^5
• 4 <= words[i].length <= 50
• 1 <= puzzles.length <= 10^4
• puzzles[i].length == 7
• words[i][j], puzzles[i][j] are English lowercase letters.
• Each puzzles[i] doesn't contain repeated characters.

 

A:

首先的想法是，把所有的都变成int.  

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        int np = puzzles.size();
        vector<int> P(np,0);

        
        for(int i =0;i<np;i++){ // change each puzzle into int
            for(auto ch : puzzles[i])
                P[i] |= (1<<(ch-'a'));
        }
        int nw = words.size();
        vector<int> W(nw,0);
        for(int i =0;i<nw;i++){ // change each word into int
            for(auto ch : words[i])
                W[i] |= (1<<(ch-'a'));
        }
        vector<int> res(np,0);
        for(int i=0;i<np;i++){
            int first = 1<< (puzzles[i][0]-'a');
            for(auto iW : W){
                if(  ( first & iW)  and ( (iW & P[i]) == iW ))
                    res[i]++;
            }
        }
        return res;
    }
};

然而，还是LTE了

好啦，直接看答案了。  key  point是 ， query的时候，因为puzzles[i].length == 7,所以我们可以直接看检查所有的subset . 这样，最多有2^7==128个

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        int np = puzzles.size();
        vector<int> P(np,0);
        for(int i =0;i<np;i++){ // change each puzzle into int
            for(auto ch : puzzles[i])
                P[i] |= (1<<(ch-'a'));
        }
        int nw = words.size();
        unordered_map<int,int> wordCount;
        for(int i =0;i<nw;i++){ // change each word into int
            int tmp = 0;
            for(auto ch : words[i])
                tmp |= (1<<(ch-'a'));
            wordCount[tmp]++;
        }
        vector<int> res;
        for(int i=0;i<np;i++){                
            int first = 1<< (puzzles[i][0]-'a');
            int puz = P[i] - first;
            vector<int> subset = getAllSubset(puz);// try all permutaion of puz (2^6 = 64 choices)
            int total = 0;
            for(int k : subset){//subset is at most 64 long
                auto iter = wordCount.find(k + first); //find() will not create default  object if not presented
                if(iter != wordCount.end())
                    total += iter->second;
            }
            res.push_back(total);
        }
        return res;
    }
private:
    vector<int> getAllSubset(int val){ // only places of 1, can be 0, no 0 bit change to 1
        if(val ==0){
            return vector<int>{0};
        }        
        int rightMostBitOf1 = val ^(val & (val-1));
        auto sub = getAllSubset(val - rightMostBitOf1);
        int len = sub.size();
        for(int i = 0;i<len;i++){
            sub.push_back(sub[i]+rightMostBitOf1);
        }
        return sub;
    }
};

这里，原版的厉害处是，没有单独计算getAllSubset(), 而是直接用数学方法计算的。

但是感觉会有多余的值。也没搞明白他到底是怎么找到所有的subset的。  不管了。 就这样了