Python Index Dictionary beating 97.6%, O(n+l) complexity, O(m) space complexity
Python Index Dictionary Solution beating 97.6%, no need to use binary search, O(n+l) complexity, O(m) space complexity, where n is length of s, m is number of w
Python Index Dictionary Solution beating 97.6%, no need to use binary search, O(n+l) complexity, O(m) space complexity, where n is length of s, m is number of words, l is the sum of length of each word in words.\n\nWhen itearating the s, for each letter c, we check every word in words, whose existing left most letter matching c. If matched, delete the left most letter. If all letters of a word are deleted, then this word is the subsequence of s. And ans is to store the answer :)\n\nThe following step optimize the above solution:\ndct is a dictionary. key is the current existing left most letter of every words, and value is a list of index i, wordLvls[i] is to maintain the index of the current existing left most letter of the words[i], which means words[i][wordlvls[i]] is the current existing left most letter of words[i]. After we delete the left most letter, wordlvls[i] will plus one, move to the next letter t, and append the index of words[i] into the dct: dct[t].append(i). Otherwise, if there\'s no next letter, the word is the subsequence of s, ans plus one. \n\nThe overall time complexity will be the length of s, plus the overall steps l, where l is sum of the length of every word in words. The space complexity is m, where m is the length of array words, as we know that the overall number of indexes store in dct will be m. \n```\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        ln = len(words)\n        dct = defaultdict(list)\n        wordLvls = [0]*ln\n        \n        for i, word in enumerate(words):\n            dct[word[0]].append(i)\n         \n        ans = 0\n        for c in s:\n            if c not in dct:\n                continue\n            lst = dct.pop(c)\n            for i in lst:\n                wordLvls[i] += 1\n                if wordLvls[i] < len(words[i]):\n                    dct[words[i][wordLvls[i]]].append(i)\n                else:\n                    ans += 1\n                        \n        return ans\n```
[]