LeetCode 792. 匹配子序列的单词数 二分查找

题目

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

思路

自己想的思路是使用一个二维数组pos，pos[i][j]记录第i个字符后面首个j字符的位置，若j字符不存在则为-1
然后遍历word的每个字符，若在遍历过程中pos[i][j] == -1，则说明无法匹配

代码如下

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        length = len(s)
        # pos[i][j]表示第i个字符后面首个j字符的位置, j用ascii码代替
        pos = [[-1] * 26 for i in range(length)]
        # fir_pos[i]表示首个i字符出现的位置
        fir_pos = [-1] * 26
        for i in range(length):
            ch = ord(s[i]) - ord('a')
            if fir_pos[ch] == -1:
                fir_pos[ch] = i

        for i in reversed(range(length - 1)):
            ch_nxt = ord(s[i + 1]) - ord('a')
            pos[i][ch_nxt] = i + 1
            for j in range(26):
                if j != ch_nxt:
                    pos[i][j] = pos[i + 1][j]
        cnt = 0
        for word in words:
            i = 0
            ch = ord(word[i]) - ord('a')
            p = fir_pos[ch]
            if p == -1:
                continue
            i = i + 1
            flag = True
            while i < len(word):
                ch = ord(word[i]) - ord('a')
                p = pos[p][ch]
                if p == -1:
                    flag = False
                    break
                i = i + 1
            if flag:
                cnt = cnt + 1
        return cnt
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

官方题解

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        pos = collections.defaultdict(list)
        for i, c in enumerate(s):
            pos[c].append(i)
        ans = len(words)
        for w in words:
            if len(w) > len(s):
                ans -= 1
                continue
            p = -1
            for c in w:
                ps = pos[c]
                j = bisect.bisect_right(ps, p)
                if j == len(ps):
                    ans -= 1
                    break
                p = ps[j]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19