[C++/Java/Python] Process by bucket - Picture explain - O(N + S)
\u231B Approach 1: Naive Brute force (Time Limit Exceeded)\n- For each word in words, check if word is a subsequence of string s.\npython\nclass Solution:\n    
**\u231B Approach 1: Naive Brute force (Time Limit Exceeded)**\n- For each `word` in `words`, check if `word` is a subsequence of string `s`.\n```python\nclass Solution:\n    def isSubsequence(self, s, t):  # Return true if `t` is a subsequence of `s`\n        i = 0\n        for c in s:\n            if i == len(t): return True\n            if c == t[i]: i += 1    \n        return i == len(t)\n        \n    def numMatchingSubseq(self, s: str, words: List[str]) -> int:\n        ans = 0\n        for word in words:\n            if self.isSubsequence(s, word):\n                ans += 1\n        return ans\n```\n**Complexity**\n- Time: `O(M * N)`, where `M <= 5000` is length of `words` array and `N <= 5*10^4` is length of string `s`\n- Space: `O(1)`\n\n---\n**\u2714\uFE0F Approach 2: Process by bucket**\n- Since length of string `s` is big, let\'s think a way to iterate chracters in string `s` once.\n- We can group `words` into buckets by their starting character.\n- Then we iterate characters `c` in string `s`, we process words in `bucket[c]` by trimming their starting character:\n\t- If the word after trimming is empty -> then it\'s a subsequence of string `s` -> `ans += 1`.\n\t- Else group the word after trimming into corresponding buckets by its starting character.\n\n**Visualize steps**\n![image](https://assets.leetcode.com/users/images/a6cea886-cbc3-4a20-a3c6-76ae3d32718c_1624447173.9917653.png)\n\n**Implementation**\n<iframe src="https://leetcode.com/playground/Rzyoji4Q/shared" frameBorder="0" width="100%" height="620"></iframe>\n\n**Complexity**\n- Time: `O(N + S)`, where `N <= 5*10^4` is length of string `s`, `S <= 5000*50` is sum length of all `words`\n- Space: `O(M)`, where `M <= 5000` is size of `words`.\n\n\nIf you **have any question, feel free to comment** below, I will try my best to answer. If you **found this post useful** for you, I\'m happy if you **give it a vote**. Thanks.
[]