Python "lazy trie"
Intuition\nDeferred the trie expansion. Use for substring case.\nFor subsequence case, directly constructure the trie and use it.\n\n# Code\npython3 []\nclass S
# Intuition\nDeferred the trie expansion. Use for substring case.\nFor subsequence case, directly constructure the trie and use it.\n\n# Code\n```python3 []\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        lazy_trie = defaultdict(list)\n        for word in words:\n            lazy_trie[word[0]] += [word]\n        \n        res = 0\n        for c in s:\n            temp = list(lazy_trie[c])\n            lazy_trie[c] = []\n            while temp:\n                word = temp.pop()\n                if len(word) == 1:\n                    res += 1\n                else:\n                    lazy_trie[word[1]] += [word[1:]]\n        return res\n```
['Python3']