Python Trie
It\'s not easy and it\'s not a typical trie, but it does work.\n\n##### Modifications to typical Trie:\n- changed the stop char $ from True/False to int to allo
It\'s not easy and it\'s not a typical trie, but it does work.\n\n##### Modifications to typical Trie:\n- changed the stop char `$` from `True/False` to `int` to allow for dupe words\n- set `$` to `0` after being used once to prevent adding to the answer again\n- delete char from Trie after being used once (optimization)\n- track `#` counter to prevent pushing or re-pushing empty Trie node (optimization)\n```\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        root = {\'$\': 0, \'#\': 0}\n        for word in words:\n            curr = root\n            for c in word:\n                if c not in curr:\n                    curr[c] = {\'$\': 0, \'#\': 0}\n                    curr[\'#\'] += 1\n                curr = curr[c]\n            curr[\'$\'] += 1\n        q = deque([root])\n        ans = 0\n        for c in s:\n            for _ in range(len(q)):\n                curr = q.pop()\n                if c in curr:\n                    curr[\'#\'] -= 1\n                    if curr[c][\'$\']:\n                        ans += curr[c][\'$\']\n                        curr[c][\'$\'] = 0\n                    if curr[c][\'#\']:\n                        q.appendleft(curr[c])\n                    del curr[c]\n                if curr[\'#\']:\n                    q.appendleft(curr)\n        return ans\n```
['Trie', 'Python']