Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- int numMatchingSubseq(string s, vector<string>& words) {
- // store indices of distinct characters seperately
- vector<int> char_index[26];
- for(int i=0;i<s.length();i++)
- char_index[s[i]-'a'].push_back(i);
- int ans = 0;
- for(auto str:words){
- // check str is the subsequence of s?
- int prev_char_index = -1;
- for(int i=0;i<str.length();i++){
- // finding current character position such that it is strictly greater than previous character position
- auto itr = upper_bound(char_index[str[i]-'a'].begin(),char_index[str[i]-'a'].end(),prev_char_index);
- // if position not found, don't increment answer
- if(itr==char_index[str[i]-'a'].end())
- goto h;
- // change prev_char_index variable and assign it to the value = current position value
- prev_char_index = *itr;
- }
- // if everything smoothly happens without the encounter of goto h statement, means subsequence found
- ans++;
- h:;
- }
- return ans;
- }
- };
Add Comment
Please, Sign In to add comment