YEZAELP

LeetCode: Number of Valid Words for Each Puzzle

Nov 17th, 2021 (edited)
176
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     int shift[27];
  5.    
  6.     int Bit(string &str){    
  7.         int len = str.size();
  8.         int alph[27];
  9.         for(int i=1;i<=26;i++)
  10.             alph[i] = false;
  11.         for(int i=0;i<len;i++){
  12.             alph[ str[i] - 'a' + 1 ] = true;
  13.         }
  14.         int bit = 0;
  15.         for(int i=1;i<=26;i++){
  16.             if(alph[i])
  17.                 bit = bit | shift[i];
  18.         }
  19.         return bit;
  20.     }
  21.    
  22.     vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
  23.        
  24.         shift[0] = 1;
  25.         for(int i=1;i<=26;i++)
  26.             shift[i] = shift[i-1] * 2;
  27.        
  28.         int nw = words.size(), np = puzzles.size();
  29.         int bitp[np + 1];
  30.         unordered_map <int, int> bitw;
  31.         for(int i=0;i<nw;i++){
  32.             bitw[ Bit(words[i]) ] ++;
  33.         }
  34.         for(int i=0;i<np;i++){
  35.             bitp[i] = Bit(puzzles[i]);
  36.         }
  37.         vector <int> ans;
  38.         for(int i=0;i<np;i++){
  39.             int cnt = 0;
  40.             int fln = puzzles[i][0] - 'a' + 1;
  41.             for(auto j: bitw){
  42.                 int bw = j.first;
  43.                 int c = j.second;
  44.                 if((bw & shift[fln]) == shift[fln] and (bitp[i] & bw) == bw)
  45.                     cnt += c;
  46.             }
  47.             ans.push_back(cnt);
  48.         }
  49.            
  50.         return ans;
  51.     }
  52. };
RAW Paste Data Copied