All 3 approaches | Buckets | Trie | Binary Search | Python
\n# Buckets: Most Optimal \n# TC: O( len(S)  + sum of all words[i] length)\n\ndef numMatchingSubseq(self, s: str, words: List[str]) -> int:\n\tstore_words = def
```\n# Buckets: Most Optimal \n# TC: O( len(S)  + sum of all words[i] length)\n\ndef numMatchingSubseq(self, s: str, words: List[str]) -> int:\n\tstore_words = defaultdict(list)\n\n\tfor word in words:\n\t\tstore_words[word[0]].append(word)\n\n\tcnt = 0\n\tfor ch in s:\n\n\t\tarr = list(store_words[ch])\n\t\tstore_words[ch] = []\n\t\twhile arr:\n\t\t\tword = arr.pop()[1:]\n\n\t\t\tif len(word) == 0:\n\t\t\t\tcnt += 1\n\t\t\telse:\n\t\t\t\tstore_words[word[0]].append(word)\n\n\treturn cnt\n```\n```\n# Trie\n\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.end = False\n        self.count = 0\n        \nclass Trie:\n    def __init__(self):\n        self.root = TrieNode()\n        \n    def insert(self, word):\n        root = self.root\n        for ch in word:\n            if ch not in root.children:\n                root.children[ch] = TrieNode()\n            root = root.children[ch] \n        root.end = True\n        root.count += 1\n            \n    \n\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        trie = Trie()\n        root = trie.root\n        \n        for word in words:\n            trie.insert(word)\n            \n        \n        def find_idx(ch, i):\n            \n            for j in range(i, len(s)):\n                if s[j] == ch:\n                    return j\n            return -1\n            \n        def solve(node, last_idx):\n            nonlocal ans\n            if node.end:\n                ans += node.count\n                \n            for ch in node.children:\n                idx = find_idx(ch, last_idx + 1)\n                if idx != -1:\n                    solve(node.children[ch], idx)\n            return\n            \n            \n        ans = 0\n        solve(root, -1)\n        return ans\n        \n```\n```\n# Binary Search\n\ndef numMatchingSubseq(self, s: str, words: List[str]) -> int:\n\t\td = defaultdict(list)\n        \n        for i, ch in enumerate(s):\n            d[ch].append(i)\n\n        def bs(ele, arr):\n            l=0\n            r= len(arr)-1\n            if arr[-1] <= ele:\n                return -1\n                \n            while l <= r:\n                mid = (r-l)//2 + l\n                if arr[mid] <= ele:\n                    l = mid + 1\n                else:\n                    r = mid - 1\n            return arr[l]\n        \n        \n        cnt = 0\n        for word in words:\n            prev = -1\n\n            for ch in word:\n                if ch not in d:\n                    break\n                idx = bs(prev, d[ch] )\n\n                if idx <= prev:\n                    break\n                \n                prev = idx\n            else:\n                cnt += 1\n        return cnt\n```\n\nIf you find this helpful, please upvote :)
['Trie', 'Binary Tree', 'Python']