792. 匹配子序列的单词数.md

792. 匹配子序列的单词数

题目传送门

点击这里

解题思路

这道题官方的做法使用了二分查找，如果双层暴力解法肯定是可以做，不过过于耗时不会ac，那么就要找如何进行优化，我们可以有如下思路，我们暴力比对，也是每次都会让s[0]去移动到和words[i][0]一样的位置去比对，我们可以实现将s的字符出现位置做好统计，然后遍历每一个words[i]，从起始位置开始，用二分法在我们事先统计位置的数组中找下一个该字符出现的位置，如果找不到则直接break，如果找到了，我们的指针索引每次都要移动，而且为了避免重复字符的影响，我们要将移动加1。这道题官方还有一种思路是多指针的思路，如果没遍历一次words都要遍历一次s，不如遍历一次s同时去处理words中的单词，这就有点并发处理的味道，其思路是，将words中的所有单词的每个字母和当前处理到的位置，遍历s，假设当前字符为v，然后对v在words中每个word的位置继续向后处理，也就是要同时处理所有word的v字符，即如果可以匹配到v，然后对应的word的指针就可以向后移动。

代码

func numMatchingSubseq(s string, words []string) int {
    // 记录s字符中每一个字符从小到大出现的索引位置
    pos := [26][]int{}
    for i, v := range s {
        pos[v-'a'] = append(pos[v-'a'], i)
    }
    res := len(words)
    for _, word := range words {
        if len(word) > len(s) {
            res --
            continue
        }
        // 利用二分法，当前word中每一个字符v，记录v出现的位置p，用二分法在我们统计出现位置数组中找到在p位置之后的第一个索引，如果是word的第一个字符，可以让p从0开始。
        p := -1
        for _, v := range word {
            index := pos[v-'a']
            i := sort.SearchInts(index, p+1) // 防止v字符是重复字符，p的位置需要相对于上次进行移动，举个例子，"abcde"，"bb"，如果p不移动b的计算会出错
            // 找不到
            if i == len(index) {
                res --
                break
            }
            p = index[i]
        }
    }
    return res
}

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
}