难度：★★★☆☆
类型：字符串
方法：桶

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。

示例:
输入:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。
注意:

所有在words和 S 里的单词都只由小写字母组成。
S 的长度在 [1, 50000]。
words 的长度在 [1, 5000]。
words[i]的长度在[1, 50]。

解答

我们用桶的思想来解决这个问题。

准备一个字典，字典的键是26个字母，字典的值是列表，作为该字母对应的桶，这个列表中包含若干字符串，这些字符串是各个单词的尾串，它们的前一个字母就是字典的键。

我们首先把各个单词放在字典中，例如["a", "bb", "acd", "ace"]这几个单词放在字典中的情况就是{'a': ['', 'cd', 'ce'], 'b': ['b']}，其他位置全部是空桶。

然后我们可以开始遍历参考字符串S中的每个字符，如果当前遍历到的字母在字典中对应的桶不是空的，那么逐个的弹出这个桶中所有的尾串，摘取其头部后将剩余部分放在该头部字母对应的桶中，以备后续的查询。如果遇到尾串已经为空，说明以该尾串对应的单词是S的一个子序列，则可以将计数器加一。

我们对S只遍历一次，循环的摘掉各个单词的头部字母，并把剩余部分安排在各自的桶中，节省了计算开销，那些遍历S结束后还留在桶中的尾串，它们对应的单词一定不是S的子序列。

class Solution(object):
    def numMatchingSubseq(self, S, words):
        ans = 0
        head_dict = {chr(i): [] for i in range(97, 97+26)}
        for word in words:
            head_dict[word[0]].append(word[1:])

        for letter in S:
            # print({k: v for k, v in head_dict.items() if v}, letter)

            bucket = head_dict[letter]
            head_dict[letter] = []

            while bucket:
                sub_word = bucket.pop()
                if not sub_word:
                    ans += 1
                else:
                    head_dict[sub_word[0]].append(sub_word[1:])
        return ans

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析