Advertisement
mickypinata

LEET-T1178: Number of Valid Words for Each Puzzle

Nov 19th, 2021
1,089
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<string> words, puzzles;
  5.  
  6. vector<int> findNumOfValidWords(vector<string> &words, vector<string> &puzzles){
  7.     map<int, int> mp;
  8.     for(string &str : words){
  9.         int btw = 0;
  10.         for(int i = 0; i < str.size(); ++i){
  11.             btw |= (1 << (str[i] - 'a'));
  12.         }
  13.         ++mp[btw];
  14.     }
  15.     vector<int> ans;
  16.     for(string &str : puzzles){
  17.         int sum = 0;
  18.         int btw = 0;
  19.         int req = 1 << (str[0] - 'a');
  20.         for(int i = 1; i < str.size(); ++i){
  21.             btw |= (1 << (str[i] - 'a'));
  22.         }
  23.         for(int b = btw; b != 0; b = (b - 1) & btw){
  24.             if(mp.find(b | req) != mp.end()){
  25.                 sum += mp[b | req];
  26.             }
  27.         }
  28.         if(mp.find(req) != mp.end()){
  29.             sum += mp[req];
  30.         }
  31.         ans.push_back(sum);
  32.     }
  33.     return ans;
  34. }
  35.  
  36. int main(){
  37.  
  38.     int nWord, nPuzzle;
  39.     scanf("%d%d", &nWord, &nPuzzle);
  40.     for(int i = 1; i <= nWord; ++i){
  41.         string str;
  42.         cin >> str;
  43.         words.push_back(str);
  44.     }
  45.     for(int i = 1; i <= nPuzzle; ++i){
  46.         string str;
  47.         cin >> str;
  48.         puzzles.push_back(str);
  49.     }
  50.     for(int x : findNumOfValidWords(words, puzzles)){
  51.         cout << x << ' ';
  52.     }
  53.  
  54.     return 0;
  55. }
  56.  
Advertisement
RAW Paste Data Copied
Advertisement