tygarian

Number of matching Subsequences leetcode

Jun 22nd, 2021 (edited)
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. class Solution {
  2. public:
  3. int numMatchingSubseq(string s, vector<string>& words) {
  4. // store indices of distinct characters seperately
  5. vector<int> char_index[26];
  6. for(int i=0;i<s.length();i++)
  7. char_index[s[i]-'a'].push_back(i);
  8. int ans = 0;
  9. for(auto str:words){
  10. // check str is the subsequence of s?
  11. int prev_char_index = -1;
  12. for(int i=0;i<str.length();i++){
  13. // finding current character position such that it is strictly greater than previous character position
  14. auto itr = upper_bound(char_index[str[i]-'a'].begin(),char_index[str[i]-'a'].end(),prev_char_index);
  15. // if position not found, don't increment answer
  16. if(itr==char_index[str[i]-'a'].end())
  17. goto h;
  18. // change prev_char_index variable and assign it to the value = current position value
  19. prev_char_index = *itr;
  20. }
  21. // if everything smoothly happens without the encounter of goto h statement, means subsequence found
  22. ans++;
  23. h:;
  24. }
  25. return ans;
  26. }
  27. };
Add Comment
Please, Sign In to add comment