Bucket by character | Intuition explained with image
If you found this post helpful, please upvote <3\n\n\n\nThe initial thought that comes into mind is to iterate over words, and for each word check if it\'s a va
If you found this post helpful, please upvote <3\n\n<hr />\n\nThe initial thought that comes into mind is to iterate over `words`, and for each word check if it\'s a valid subsequence of string `s`\n\nThe code would look like this:\n\n```\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        if not words or not s: return 0\n        \n        ans = 0\n        for word in words:\n            if self.is_subsequence(s, word):\n                ans += 1\n        return ans\n        \n    \n    def is_subsequence(self, s: str, ss: str) -> bool:\n        if len(ss) > len(s): return False\n        \n\t\t# sub string pointer\n        ss_p = 0\n\t\t\n\t\t# s_p = string pointer\n        for s_p in range(len(s)):\n            if ss[ss_p] == s[s_p]:\n                ss_p += 1\n\t\t\t\t# if we matched the whole sub string\n                if ss_p == len(ss):\n                    return True\n        return False\n```\n\nThis solution gets TLE.\n\n# Small optimization\nWe can do a small optimization which is acutally AC, but I wouldn\'t recommend it as a final solution.\n\nWe can cache words that have been processed already, if we have a duplicate word in `words` array, we can know in O(1) if it\'s a valid subsequence or not, by checking the cache\n\n```\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        if not words or not s: return 0\n        \n        cache = {}\n        ans = 0\n        for word in words:\n            if self.is_subsequence(s, word, cache):\n                ans += 1\n        return ans\n        \n    \n    def is_subsequence(self, s: str, ss: str, cache: dict[str, bool]) -> bool:\n        if len(ss) > len(s): return False\n        \n        ss_p = 0\n        \n        if ss in cache:\n            return cache[ss]\n            \n        for s_p in range(len(s)):\n            if ss[ss_p] == s[s_p]:\n                ss_p += 1\n                if ss_p == len(ss):\n                    cache[ss] = True\n                    return True\n        cache[ss] = False\n        return False\n```\n\n\n# Bucket by characters\nThe optimized solution is to iterate over the string `s` just once.\n\nWe can bucket the words in `words` array by their starting character, it would look like this in the beginning:\n\n![image](https://assets.leetcode.com/users/images/b92c292d-78dc-476c-a2d8-08bc09f41697_1658322344.8964515.png)\n\nWhenever we process a character in `s`, we update the words in the corresponding bucket of that character.\n\nFor example s[0] = \'a\', we update the \'a\' bucket:\n\n![image](https://assets.leetcode.com/users/images/e624d4cc-bbf8-477c-91d9-eefbb634b693_1658322434.3182838.png)\n\nWe continue this process for all characters in `s`.\n\nWhenever we find a word inside a bucket with length 1, this means we found a full subsequence, we update our answer by 1.\n\n# Algorithm\n```\nfrom collections import defaultdict, deque\n\nclass Solution:\n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        buckets = defaultdict(lambda: deque([]))\n        for word in words:\n            buckets[word[0]].append(word)\n        \n        answer = 0\n        for c in s:\n            for i in range(len(buckets[c])):\n                word = buckets[c].popleft()\n                # last character\n                if len(word) == 1:\n                    answer += 1\n                    continue\n                \n                buckets[word[1]].append(word[1:])\n                \n        return answer\n```
['Python']