Number of Valid Words for Each Puzzle

Jin Shang bio photo By Jin Shang

With respect to a given puzzlewordvalid

  • 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 answeranswer[i]wordspuzzles[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.

Solution:

Use bitmap to store each string in word. 1 for presense of letter c-‘a’. Use map to store count for each word bitmap.

Because puzzle length = 7, and the first one must be present, so there are 2^6 = 64 possiblities for each puzzle. Generate the possibilities and add up the counts.

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int,int> ws;
        for(int i = 0;i < words.size(); i++){
            string w = words[i];
            int temp = 0;
            int cnt = 0;
            for(char c: w){
                if(temp & (1<<(c-'a'))) continue;
                cnt++;
                if(cnt > 7) break;
                temp |= (1 << (c-'a'));
            }
            if(cnt>7) continue;
            ws[temp]++;
        }
        
        vector<int> ans(puzzles.size(), 0);
        for(int i=0;i<puzzles.size();i++){
            string p = puzzles[i];
            
            for(int j = 0; j< (1<<6); j++){
                int ptemp = (1 << (p[0] - 'a'));
                for(int k = 0; k < 6;k++){
                    if(j & (1<<k)){
                        ptemp |= (1<< (p[k+1] - 'a'));
                    }
                }
                
                ans[i] += ws[ptemp];
            }
        }
        return ans;
    }
};