原题链接:
https://leetcode.cn/problems/number-of-matching-subsequences/

法1:分桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

func numMatchingSubseq(s string, words []string) int {
	// 以每个首字母为分类的桶
	d := make([][]string,26)
	// 初始分桶
	for _, w := range words {
		u := w[0] - 'a'
		d[u] = append(d[u], w)
	}
    //fmt.Println(d)
	/*
		进行分桶判断
		如果当前桶的长度为1 且包含在s中 则ans++
		如果当前包含而不为1 则去掉当前的首字母 按照新的首字母重新分桶
	*/
	ans := 0
	for i := 0; i < len(s); i++ {
		u := s[i] - 'a'
		for _, w := range d[u] {
			if w[0] - 'a' == u {
				if len(w) == 1 {
					ans++
				} else {
					// 去除首字母后 按照新的首字母重新分桶
					d[w[1]-'a'] = append(d[w[1]-'a'], w[1:])
				}
			}
            // 如果第一个字符相等的话 那么经过以上操作后 当前操作的串就要排除了
            // 如果不相等由于是按顺序遍历的 所以相对顺序一定是不等的也直接排除
            d[u] = d[u][1:]
		}
	}

	return ans
}

法2: 二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package main

import (
	"sort"
)

/*
	二分:
	哈希存储s 中每个字母出现的下标
	遍历中words 每个word w
	对于word中的每个字母c
	先将指针i指向-1 在d[c]中二分查找第一个大于i的位置j
	(因为相对顺序要一样c在s中出现的位置一定要在上一个位置i之后 所以是第一个大于i的位置j)
*/

func numMatchingSubseq(s string, words []string) int {
	d := [26][]int{}
	// 建立hash ch -> i
	for i, ch := range s {
        u := ch - 'a'
		d[u] = append(d[u], i)
	}

	check := func(w string) bool {
		// 初始位置为 -1
		i := -1
		for k := 0; k < len(w); k++ {
			c := w[k] - 'a'
			// 返回的是大于i的第一个位置 所以二分找的是i+1 且go本身二分就是右端点二分
			j := sort.SearchInts(d[c], i+1)
			// 出界 那么这个点就不存在
			if j == len(d[c]) {
				return false
			}
			i = d[c][j]
		}

		return true
	}
	ans := 0
	for _, w := range words {
		if check(w) {
			ans++
		}
	}
	return ans
}