Python: Explained All Possible Solutions with time and space complexity
To solve this problem we can have multiple approaches but all approaches may not fit the constraints right. Let\'s say n = length of s, m = len of words array, 
To solve this problem we can have multiple approaches but all approaches may not fit the constraints right. Let\'s say n = length of s, m = len of words array, and k = max length of the strings in the words array.\n\n**Method 1**: \n1. Generate all possible subsequences of \'s\'. ------- O(2^n) ------- ***TLE***\n2. Compare them with the strings in words and get the answer. --------- O(m * k) \n\n**Method 2**:\n1. Generate all possible subsequences using DP. ----- O(n^2) = O((5 * 10^4)^2) > O(10^8) ----- ***TLE***\n2.  Compare them with the strings in words and get the answer. --------- O(m * k) \n\nSo, we can clearly see generating subsequences won\'t help.\n\n**Method 3**: ------ ***ACCEPTED***\n1. Check if all strings in words is a subsequence of s, one by one.\nA. Checking if \'s\' is a subsequence of \'t\', takes O(max( len(s), len(t) ) ) time = O(n) time and O(n) space for stack.\n![image](https://assets.leetcode.com/users/images/ca6c8ca9-afee-4521-a283-c9c5de5ef353_1624350535.687156.png)\nB. Checking for all the strings in words takes O(m) time.\nSo **total time = O(n * m)** = O((5 * 10^4) * (5 * 10^3)) == 10 ^ 8 which is the exact threshhold for TLE.\n\nNow, this method gives TLE as the bounds are too strict.\n\nAs we are in a close boundary of Getting TLE, we can **cache the outputs** *(Accepted)* such that if the same string in words is repeated, we do not need to compute the subsequence again.\n\nE.g.: If the input is something like this, we can avoid a lot of recomputations.\n```\n\'lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllmmmmmmmmmmmmmmmmmmmmmvvvvvvvvvvvvvvvvwwwwwwwwwwww\'\n[\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lv\',\'lm\',\'lm\',\'lw\']\n```\n\nSo, store the output of previous computation, so that we can use it again without actually computing, if the same set of inputs comes again (Kind of memoization).\n\nFull Code:\n```\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        def issubseq(s,t):\n            stack = []\n            for i in t:\n                stack.append(i)\n            \n            n = len(s)\n            for i in range(n-1,-1,-1):\n                if not stack:\n                    return True\n                if stack[-1] == s[i]:\n                    stack.pop()\n            return stack == []\n        \n        \n        hashmap = {}\n        \n        count = 0\n        for word in words:\n            if word not in hashmap:\n                if issubseq(s,word):\n                    count += 1\n                    hashmap[word] = True\n                else:\n                    hashmap[word] = False\n            else:\n                if hashmap[word]:\n                    count += 1\n        return count\n```\n\nTime = O(n * m) and Space = O(n) for stack. \n\n***But, Can\'t we do better? Is there any further scope for improvement? Let\'s find out.***\n\nWhat if we store all the indices of each character in \'s\' in a hashmap?\nE.g.: s = \'abcded\'\nindices = {\'a\': [0], \'b\': [1], \'c\': [2], \'d\': [3,5], \'e\':[4]} \nHow will this help? -> When we are checking for sequences, we can directly check based on increasing indices.\nE.g.: If word = \'acded\', we can maintain a variable called current_position = -1,\nNow, we look for position of \'a\', pos = 0, current_position < pos, so current_position = pos = 0.\nThen, we look for position of \'c\', pos = 2, current_position < pos, current_position = pos = 2.\nThen, we look for position of \'d\', pos = 3 (we choose from left to right), current_position < pos, current_position = pos = 3.\nThen, we look for position of \'e\', pos = 4, current_position < pos, current_position = pos = 4.\nThen, we look for position of \'d\', pos = 3(we choose from left to right) , current_position >= pos, is there any other position of \'d\'? -> Yes, pos = 5, now current_position < pos, so current_position = pos = 5.\n\nNow, we have found all the characters in word in the indices hashmap, and in increasing order of their indices. Hence return true.\n\nNow suppose, our word was \'bb\' and current_position = -1.\nThen, we look for position of \'b\', pos = 1, current_position < pos, current_position = pos = 1.\nThen, we look again for position of second \'b\', pos = 1, current_position >= pos, is there any other position of b? -> NO, so we did not find the desired subsequence, Hence return False.\n\nBut isn\'t this the same method? What\'s the time complexity?\nYes, this is the same method as using stack, and even the time compleixty is same max(n,k) = O(n) for checking subsequences, only because we are performing linear search on the indices.\n\nIs there any scope for binary search on the indices? -> Yes, because the indices are added sequentially, they always remain sorted. Hence, instead of searching sequentially, we can perform binary search over indices here.\n\nE.g.: lets say we are looking for \'c\' in indices and current_position = 3, and indices[c] = [1,2,4,6].\nHere the correct position to insert current_position = 3 would be the index 2 with value 4. Such that it becomes [1,2,3,4,6] but wait... we are not going to insert. we just want the index, once we got the index, we can choose that element and make it pos, now current_position < pos, so we can update the current position = pos = 4.\nSo problem of sequential searching is solved. \n\nNow, we have bisect_left function that gives us the first occurance of elemnt \'>= x\'. and bisect_right gives us the last occurance of element \'<=x\' + 1 in a sorted array in logarithmic time. Hence, it can mimic binary search. So, we have used bisect_right here as we want the greater element.\n\n**Method 4**: Binary Search on Indices: ----- ***ACCEPTED*** (Best Approach)\nJust modified the above caching code to perform binary search on indices.\n```\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        def issubseq(t):\n            current_pos = -1\n            stack = []\n            for i in t:\n                if indices[i]:\n                    pos = bisect.bisect_right(indices[i], current_pos)\n                    if pos == len(indices[i]):\n                        return False\n                    current_pos = indices[i][pos]\n                else:\n                    return False\n            return True\n        \n        \n        \n        indices = defaultdict(list)\n        for i, c in enumerate(s):\n            indices[c].append(i)\n        \n                \n        hashmap = {}\n        \n        count = 0\n        for word in words:\n            if word not in hashmap:\n                if issubseq(word):\n                    count += 1\n                    hashmap[word] = True\n                else:\n                    hashmap[word] = False\n            else:\n                if hashmap[word]:\n                    count += 1\n        return count\n```\nTime = O(m log n) and space = O(n) for indices hashmap.\n\nI hope it helps!
['Binary Tree', 'Python']