1178. Number of Valid Words for Each Puzzle

문제: https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/

Number of Valid Words for Each Puzzle - LeetCode

 

class Solution {
public:    
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> wordCount;
        for(int i = 0; i < words.size(); i++){
            int t = 0;
            for(int j = 0; j < words[i].size(); j++){
                t |= (1 << (words[i][j] - 'a'));
            }
            wordCount[t]++;
        }
        
        vector<int> ans;
        
        for(int i = 0; i < puzzles.size(); i++){
            int t1 = 0;
            int firstChar = 1 << (puzzles[i][0] - 'a');
            int cnt = wordCount[firstChar];
            
            int mask = 0;
            for(int j = 1; j < puzzles[i].size(); j++){
                mask |= (1 << (puzzles[i][j] - 'a'));
            }
            
            for(int submask = mask; submask; submask = (submask - 1) & mask){
                cnt += wordCount[submask | firstChar];
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};

-> 공부필요...

 

https://leetcode.com/explore/learn/card/trie/ 공부예정