Python Implicit/Lazy Trie
Idea is that if we have a trie built from all the words given, then we can simply go through each character in S and at each step keep track of what are the cur
Idea is that if we have a trie built from all the `words` given, then we can simply go through each character in `S` and at each step keep track of what are the current characters we need. If the current character is needed, then go down the trie at each of these needed nodes, and then for the children of these met needs, add them to `needs`. \n\nBut we don\'t really need to build the trie up front, because we just need to initialize the `needs` dictionary with the first characters of each word. Everytime we satisfy the need character, just go to the next character in the word. Building the trie would actually lead to TLE.\n\n```python\nfrom collections import defaultdict\n\nclass Solution(object):\n    def numMatchingSubseq(self, S, words):\n        needs = defaultdict(list)\n        for word in words:\n            needs[word[0]].append((0, word))\n        matches = 0\n        for c in S:\n            met_needs = needs[c]\n            needs[c] = []\n            for i, w in met_needs:\n                if i+1 >= len(w):\n                    matches += 1\n                    continue\n                needs[w[i+1]].append((i+1, w))\n        return matches\n```
[]