0792.匹配子序列的单词数

https://leetcode.cn/problems/number-of-matching-subsequences/

方法一：二分搜索

时间复杂度 $O(m \log n)$，空间复杂度 $O(n)$。

func numMatchingSubseq(s string, words []string) int {
	ans := 0
	index := [256][]int{}
	for i, c := range s {
		index[c] = append(index[c], i)
	}
	var isSubseq = func(s, word string) bool {
		target := 0
		for _, c := range word {
			if len(index[c]) == 0 {
				return false
			}
			bound := leftBound(index[c], target)
			if bound == -1 {
				return false
			}
			target = index[c][bound] + 1
		}
		return true
	}

	for _, word := range words {
		if isSubseq(s, word) {
			ans += 1
		}
	}
	return ans
}

func leftBound(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for mid := (l + r) / 2; l <= r; mid = (l + r) / 2 {
		if nums[mid] >= target {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	if l >= len(nums) {
		return -1
	}
	return l
}