Leetcode 792. Number of Matching Subsequences

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，每个单词都与s进行遍历比较，超时。Version 2，先将s中的字符以及对应的索引保存到字典中，相同字符对应的索引构成一个有序序列，然后依次遍历每个单词的每个字符，在s中查找其对应的字符索引位置，如果字符在s中不存在，直接跳出循环，pre表示单词中前一个字符在s中的索引位置，每次查找使用二分查找，如果返回的序列索引位置等于序列的长度，即pre位置之后的s中没找到对应的当前字符，否则，更新pre为当前字符在s中的索引位置，flag表示是否满足条件，初始设为True，当不满足条件跳出循环时，设为False，每个单词根据flag的值来统计满足条件的单词个数。

• Version 1

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        count = 0
        n = len(s)
        for word in words:
            m = len(word)
            if m > n:
                continue
            i = 0
            j = 0
            while i < n and j < m:
                if s[i] == word[j]:
                    i += 1
                    j += 1
                else:
                    i += 1
                if m - j - 1 > n - i - 1:
                    break
            if j == m:
                count += 1
        return count

• Version 2

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        count = 0
        stat = collections.defaultdict(list)
        for i, ch in enumerate(s):
            stat[ch].append(i)
        for word in words:
            flag = True
            pre = -1
            for ch in word:
                if ch not in stat:
                    flag = False
                    break
                index = bisect.bisect(stat[ch], pre)
                if index == len(stat[ch]):
                    flag = False
                    break
                else:
                    pre = stat[ch][index]
            if flag:
                count += 1
        return count

Reference

1. https://leetcode.com/problems/number-of-matching-subsequences/