【2022-11-17每日一题】792. 匹配子序列的单词数[Medium]

2022-11-17每日一题：792. 匹配子序列的单词数

难度：Medium

标签：字典树 、 哈希表 、 字符串 、 排序

给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

• 例如， “ace” 是 “abcde” 的子序列。

示例 1:

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

Example 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

提示:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• words[i]和 s 都只由小写字母组成。

方法一：分桶

• 详细解释

func numMatchingSubseq(s string, words []string) (ans int) {
    d := [26][]string{}
    for _, w := range words {
        d[w[0]-'a'] = append(d[w[0]-'a'], w) // 按首字母分桶
    }
    for _, c := range s {
        q := d[c-'a']
        d[c-'a'] = nil
        for _, t := range q {
            if len(t) == 1 { // 长度加一
                ans++
            } else {
                d[t[1]-'a'] = append(d[t[1]-'a'], t[1:]) // 按第二个字母继续分桶
            }
        }
    }
	return ans
}

复杂度分析

方法二：分桶优化（多指针）

// 写法一：
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'] = []pair{}
        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 ans
}

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

复杂度分析

方法三：二分查找

• 推荐题解

// 写法一：
func numMatchingSubseq(s string, words []string) (ans int) {
    pos := [26][]int{}
    for i, c := range s {
        pos[c-'a'] = append(pos[c-'a'], i)
    }
    check := func(w string) bool {
        i := -1
        for _, c := range w {
            t := pos[c-'a']
            j := sort.SearchInts(t, i+1) // 二分查找大于t的第一个下标
            if j == len(t) {
                return false
            }
            i = t[j]
        }
        return true
    }
    for _, w := range words {
        if check(w) {
            ans++
        }
    }
    return ans
}

// 写法二：
func numMatchingSubseq(s string, words []string) int {
    pos := [26][]int{}
    for i, c := range s {
        pos[c-'a'] = append(pos[c-'a'], i)
    }
    ans := len(words)
    for _, w := range words {
        if len(w) > len(s) { // 小优化
            ans--
            continue
        }
        p := -1
        for _, c := range w {
            ps := pos[c-'a']
            j := sort.SearchInts(ps, p+1)
            if j == len(ps) {
                ans--
                break
            }
            p = ps[j]
        }
    }
    return ans
}

复杂度分析

LeetCode题库地址

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