vivek_ragi

Number_of_Matching_Subsequences

Jun 22nd, 2021
711
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.         vector<vector<int>> alpha (26);
  2.         for (int i = 0; i < S.size (); ++i) alpha[S[i] - 'a'].push_back (i);
  3.         int res = 0;
  4.         //ace
  5.         for (const auto& word : words) {
  6.             int x = -1;
  7.             bool found = true;
  8.  
  9.             for (char c : word) {
  10.                 auto it = upper_bound (alpha[c - 'a'].begin (), alpha[c - 'a'].end (), x);
  11.                 if (it == alpha[c - 'a'].end ()) found = false;
  12.                 else x = *it;
  13.             }
  14.  
  15.             if (found) res++;
  16.         }
  17.  
  18.         return res;
  19.     }
RAW Paste Data