Leetcode-每日一题792. 匹配子序列的单词数（分桶）

题目链接：https://leetcode.cn/problems/number-of-matching-subsequences/description/

思路

方法一、分桶

题目意思：给你一个字符串 s 和字符串数组 words， 可以对字符串 s 某些位置上的字符进行删除，并不改变原来的字符顺序产生的子序列，去对比字符串数组 words 存在多少相同的数量。

我原本的思路是通过去重+暴力，发现卡在41的样例超时了，发现了一个问题，有很多字符串不需要去判断，大大浪费了时间，那我们去找那些我们需要的不就行了，通过对字符串数组 words 中每个字符串的首字母，放入桶内：

a:["a","acd","ace"]
b:["bb"]
1
2

遍历字符串的字符，去消除对应桶内的字符串，去生成新的桶，例如字符串 s = “abcde”，我们读取到第一个字符 a 时，可以去直接处理桶a，得到的结果：

a:[]
b:["bb"]
c:["cd","ce"]
1
2
3

通过上述操作，我们不断获得新的桶，直到字符串 s 遍历完，真正的子序列也会被筛选啊出来。

有个问题，我们怎么统计答案呢？很简单我们只需要去判断当前桶内的字符串长度已经等于 1 的时候，我们这个字符串就是字符串 s 的子序列。

代码示例

func numMatchingSubseq(s string, words []string) (ans int) {
	ton := [26][]string{}
    for _, w := range words {
        ton[w[0] - 'a'] = append(ton[w[0] - 'a'], w)
    }
    for _, c := range s {
        q := ton[c - 'a']
        ton[c - 'a'] = nil
        for _, t := range q {
            if len(t) == 1 {
                ans++
            }else {
                ton[t[1] - 'a'] = append(ton[t[1] - 'a'], t[1:])
            }
        }
    }
	return
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析

• 时间复杂度：O(n+ sum∣w i​∣)，其中 n 和 m 分别为 s 和 words 的长度，而 ∣wi 为 words[i] 的长度，遍历一次字符串s需要O(n)的时间，sum∣w i​∣ 是 $$\sum _{i=0}^m\mid wi$$，分桶需要O(sum∣w i​∣)的时间。
• 空间复杂度：O(m)，其中 m 是 words 的长度