C++ || Two Pointer || Hashmap || Subsequence || 14 Lines code
Really good problem to understand the constraints, and discuss different approaches.\nThe first standard approach that I came up with resulted in TLE as expecte
***Really good problem*** to understand the constraints, and discuss different approaches.\nThe **first** *standard approach* that I came up with resulted in **TLE** as expected.\nThen even the **second** approach that I wrote was failing for few test cases where I understood the need to *remove reduntant queries which are already processed*.\n\nFinally, I wrote the correct approach which got AC!\nThere are few other approches including DP and binary search which can *reduce the time required for searching the specific word in words array*.\nHere I am mentioning all the approches that I worked on.\n\n***EDIT:*** \n\t1. Try passing strings by reference, it will improve the space complexity as well as help in reducing time complexity to certain extent.\n\t2. Try using unordered_map instead of map.\n\n**Approach 1:** \n***Result:*** *TLE (21/ 52)*\n```\nclass Solution {\npublic:\n    bool isSubsequence(string s1, string s2, int m, int n){\n\t\t//Here I am simply traversing through strings recursively and checking the last characters\n\t\t//resulting in TLE as it will take a lot of time to process all the subsequences.\n\t\t\n\t\t//if end of s2 then our goal is fulfilled as we have traversed s2 completely.\n        if(n == 0) return true;\n\t\t\n\t\t//else return false, as we reached end of s1 without reaching end of s2\n        if(m == 0) return false;\n\t\t\n\t\t//if matched call recursively for next characters in both strings\n        if(s1[m - 1] == s2[n - 1]) return isSubsequence(s1, s2, m - 1, n - 1);\n\t\t\n\t\t//if not simply reduce s1 by 1 and call again\n        else return isSubsequence(s1, s2, m - 1, n);\n    }\n    int numMatchingSubseq(string s, vector<string>& words) {\n        int count = 0;\n        for(auto x: words){\n            count += (isSubsequence(s, x, s.size(), x.size()) == true);\n        }\n        return count;\n    }\n};\n```\n\n**Approach 2:**\n***Result:*** *TLE (43/52)*\n```\nclass Solution {\npublic:\n    bool isSubsequence(string s1, string s2, int m, int n){\n\t\t//Here we have simplified the process in finding whether the subsequence is there or not in O(n)\n\t\t// Variable for s2 string\n        int j = 0;\n        for(int i = 0; i < m && j < n; i++){\n\t\t\t// if matched increment both variables, else just increment i\n            if(s1[i] == s2[j]) j++;\n        }\n\t\t//if we reached end of s2 that means all the characters of s2 have occurred in s1, so return true;\n        return j == n;\n    }\n    int numMatchingSubseq(string s, vector<string>& words) {\n        int count = 0;\n        for(auto x: words){\n            count += (isSubsequence(s, x, s.size(), x.size()) == true);\n        }\n        return count;\n    }\n};\n```\n\n**Approach 3:**\n***Result:** AC (52/52)*\n\nThe above solution *fails* because we\'ve not taken into consideration that there might be cases where we might encounter strings for which *we have already calculated whether this string is subsequence or not.* So for that purpose we use *hashmap*! *Kudos*!\n```\nclass Solution {\npublic:\n    bool isSubsequence(string s1, string s2, int m, int n){\n\t\t//This function behaves simliar to the one in previous approach\n        int j = 0;\n        for(int i = 0; i < m && j < n; i++){\n            if(s1[i] == s2[j]) j++;\n        }\n        return j == n;\n    }\n    int numMatchingSubseq(string s, vector<string>& words) {\n        int count = 0;\n\t\t\n\t\t//Hashmap with string and bool pair\n\t\t// Storing whether a string is subsequence or not!\n        map<string, bool> mp;\n        for(auto x: words){\n\t\t\n\t\t\t//if the string has already occurred then don\'t compute again\n            if(mp.find(x) != mp.end()) {\n\t\t\t\t// if that string has value true that means it is subsequence, count++\n                if(mp[x] == true) {\n                    count++;\n                }\n\t\t\t\t//if not, go for next string\n                continue;\n            }\n\t\t\t\n\t\t\t// if not calculated previously, compute the value and assign to x(current string from words)\n            mp[x] = isSubsequence(s, x, s.size(), x.size());\n            count += (mp[x] == true);\n        }\n\t\t// return the final count of number of subsequences.\n        return count;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']