Python | Trie
This is not the best solution memory wise, but it is a beginner friendly aproach introducing tries.\n\nThe idea is to create a trie that contains all the words 
This is not the best solution memory wise, but it is a beginner friendly aproach introducing <a href="https://en.wikipedia.org/wiki/Trie">tries</a>.\n\nThe idea is to create a trie that contains all the words in `words`. Then search through each branch to see if the branch leads to a substring. The trick is to also keep track of the number of repeated words in the list, since the trie would not be able to *see* multiple copies of the same word.\n\nTo implement the trie, we\'ll use nested dictionaries. To mark the end of a word in the trie we\'ll use `None`, and `node[None]` will keep track of how many copies of the word we have in `words`.\n\n```\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        \n        def insert_in_trie(word: str):\n            curr = trie\n            for char in word:\n                if char not in curr:\n                    curr[char] = {}\n                curr = curr[char]\n            if None in curr:\n                curr[None] += 1  # keeps count of repeated words\n            else:\n                curr[None] = 1\n            \n        S = len(s)\n        trie = {}\n        for word in words:\n            insert_in_trie(word)\n        ans = 0\n\t\t# queue contains tuples (node, idx), where node is the last visited node on the current\n\t\t# branch, and idx is indicates that so far the branch is a subsequence of s[:idx]\n        queue = [(trie, 0)]\n        while queue:\n            curr, i = queue.pop()\n            for char in curr:\n                if char == None:\n                    ans += curr[None]\n                else:\n                    for j in range(i, S):\n                        if s[j] == char:\n                            queue.append((curr[char], j + 1))\n                            break\n        return ans\n```
['Trie', 'Python']