3 Python Solutions
1- Basic one that gives TLE\n\nclass Solution:\n    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n        count=0\n        for w in words:\n   
1- Basic one that gives TLE\n```\nclass Solution:\n    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n        count=0\n        for w in words:\n            i=0\n            j=0\n            while(j<len(w) and i<len(S)):\n                if w[j]== S[i]:\n                    j+=1\n                    i+=1\n                else:\n                    i+=1\n            if j== len(w):\n                count+=1\n        return count\n```\n\n2- Keeping track of indexes in S\n```\nclass Solution:\n    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n        count=0\n        indexes= collections.defaultdict(list)\n        \n        for i,c in enumerate(S):\n            indexes[c].append(i)\n        \n        for w in words:\n            minim=-1\n            for c in w:\n                if c not in indexes:\n                    minim=-1\n                    break\n                for i in indexes[c]:\n                    found= False\n                    if i> minim:\n                        minim= i\n                        found=True\n                        break\n                if not found:\n                    minim=-1\n                    break\n            if minim!= -1:\n                count+=1\n                \n        return count\n```\n\n3- Using trie approach and matching characters in parallel\n\n```\nclass Solution:\n    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n        count=0\n        needed= collections.defaultdict(list)\n        \n        for w in words:\n            needed[w[0]].append((1, w))\n        \n        for c in S:\n            if c in needed:\n                nextUps= needed[c]\n                del needed[c]\n                for i,w in nextUps:\n                    if i== len(w):\n                        count+=1\n                    else:\n                        needed[w[i]].append((i+1, w))\n        return count\n```\n            \n                \n                    \n                \n                \n                    \n                \n\n\n            \n                \n                    \n
[]