golang 解法, 执行用时: 40 ms, 内存消耗: 9.2 MB, 提交时间: 2022-11-17 10:31:05

func numMatchingSubseq(s string, words []string) (ans int) {
	type pair struct{ i, j int }
	d := [26][]pair{}
	for i, w := range words {
		d[w[0]-'a'] = append(d[w[0]-'a'], pair{i, 0})
	}
	for _, c := range s {
		q := d[c-'a']
		d[c-'a'] = nil
		for _, p := range q {
			i, j := p.i, p.j+1
			if j == len(words[i]) {
				ans++
			} else {
				d[words[i][j]-'a'] = append(d[words[i][j]-'a'], pair{i, j})
			}
		}
	}
	return
}

golang 解法, 执行用时: 84 ms, 内存消耗: 8.1 MB, 提交时间: 2022-11-17 10:30:46

func numMatchingSubseq(s string, words []string) (ans int) {
	d := [26][]int{}
	for i, c := range s {
		d[c-'a'] = append(d[c-'a'], i)
	}
	check := func(w string) bool {
		i := -1
		for _, c := range w {
			t := d[c-'a']
			j := sort.SearchInts(t, i+1)
			if j == len(t) {
				return false
			}
			i = t[j]
		}
		return true
	}
	for _, w := range words {
		if check(w) {
			ans++
		}
	}
	return
}

python3 解法, 执行用时: 476 ms, 内存消耗: 18.8 MB, 提交时间: 2022-11-17 10:30:19

'''
我们还可以先用数组或哈希表 d 存放字符串 s 每个字符的下标，即 d[c] 为 s 中所有字符 c 的下标组成的数组。
然后我们遍历 words 中的每个单词 w，我们通过二分查找的方法，判断 w 是否为 s 的子序列，是则答案加 1。判断逻辑如下：

1.定义指针 i 表示当前指向字符串 s 的第 i 个字符，初始化为 -1。
2.遍历字符串 w 中的每个字符 c，在 d[c] 中二分查找第一个大于 i 的位置 j，如果不存在，则说明 w 不是 s 的子序列，直接跳出循环；
否则，将 i 更新为 d[c][j]，继续遍历下一个字符。
3.如果遍历完 w 中的所有字符，说明 w 是 s 的子序列。
'''
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        def check(w):
            i = -1
            for c in w:
                j = bisect_right(d[c], i)
                if j == len(d[c]):
                    return False
                i = d[c][j]
            return True

        d = defaultdict(list)
        for i, c in enumerate(s):
            d[c].append(i)
        return sum(check(w) for w in words)

python3 解法, 执行用时: 464 ms, 内存消耗: 16.8 MB, 提交时间: 2022-11-17 10:25:08

'''
按首字母分桶，
'''
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        d = defaultdict(deque)
        for i, w in enumerate(words):
            d[w[0]].append((i, 0))
        ans = 0
        for c in s:
            for _ in range(len(d[c])):
                i, j = d[c].popleft()
                j += 1
                if j == len(words[i]):
                    ans += 1
                else:
                    d[words[i][j]].append((i, j))
        return ans