Did not find this simple approach, so adding it here [Video]
In the brute force approach we iterate through each word in words, and compare it against s every time. Not sharing the code for this, however the time complexi
In the brute force approach we iterate through each word in words, and compare it against s every time. Not sharing the code for this, however the time complexity is\nO(n x (wsize + ssize)) where n is size of words list, wsize is maximum size of a word and ssize is maximum size of s. \n\nIf we could somehow check whether a word is a subseq in O(wsize) instead of O(wsize + ssize) time this will help us get AC. In the bruteforce approach when we check each character of word, all we are concerned about is the next occurrence of the character in s. One thing we can do is store the next index of occurrence of a character from a given index in a 2D array(say smap). So, for \'abcde\' next occurrence of d from index 1 is 3 so smap[1][\'d\'] = 3. If a character is not present in the rest of the string we store -1. This way we will not have to iterate through non essential characters and can directly find the next index or know it is not present. \nC++ code based on this idea is -\n\n```cpp\n\tbool isSubSeq(vector<vector<int>> &smap, string word, int ssize) {\n        int curIdx = 0;\n        for(int i = 0; i < word.size(); ++i) {\n            int nextpos = smap[curIdx][word[i]];\n            if(nextpos == -1 || (i != word.size()-1 && nextpos == ssize-1))\n                return false;\n            curIdx = nextpos+1;\n        }\n        return true;\n    }\n    \n    int numMatchingSubseq(string s, vector<string>& words) {\n        vector<vector<int>> smap(s.size(), vector<int>(256, -1));\n        for(int i = (int)s.size()-1; i >= 0; --i) {\n            if(i+1 < s.size()) smap[i] = smap[i+1];\n            smap[i][s[i]] = i;\n        }\n        \n        int ans = 0;\n        for(auto &word: words)\n            if(isSubSeq(smap, word, s.size())) ans++;\n        \n        return ans;\n    }\n```\n\nDo comment here to point out anything important I might have missed, or if the code can be simplified further. Leave a like if you find this easy to understand and code :)\nAlso checkout Gaurav\'s video below if you want a little binary search practise from the question.
['C']