判断子序列 -- 二分查找

392. 判断子序列

792. 匹配子序列的单词数

class Solution:
    """

    """
    def isSubsequence(self, s: str, t: str) -> bool:
        """
        双指针
        时间复杂度：O(n)
        空间复杂度：O(1)
        392. 判断子序列
        https://leetcode.cn/problems/is-subsequence/description/
        :param s:
        :param t:
        :return:
        """
        i, j = 0, 0

        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

    def isSubsequence2(self, s: str, t: str) -> bool:
        """
        假设s和t的长度分别为m和n，n>>m，如果处理多个s，按照上述线性扫描的方法，时间复杂度为
        O(mn)，现在给一种二分查找的方式，时间复杂度可降低为O(mlogn)

        :param s:
        :param t:
        :return:
        """
        # 对字符串t进行预处理，将每个字符出现的索引位置按顺序存到数组里
        idx = [[] for _ in range(256)]
        for i, c in enumerate(t):
            idx[ord(c)].append(i)

        # 串t上的指针
        j = 0
        # 借助 index 查找 s[i]
        for i, c in enumerate(s):
            # 整个t就没有c
            if not idx[ord(c)]:
                return False
            pos = self.left_bound(idx[ord(c)], j)
            # 二分查找没有找到字符c
            if pos == -1:
                return False
            # 向前移动指针j
            j = idx[ord(c)][pos] + 1
        return True

    def left_bound(self, arr, target):
        """
        左侧边界的二分查找，若找到返回索引，若不存在，则返回比target大的第一个元素的索引，
        若不存在比target大的元素，返回-1
        :param arr:
        :param target:
        :return:
        """
        l, r = 0, len(arr)
        while l < r:
            mid = l + (r-l)//2
            if arr[mid] >= target:
                r = mid
            else:
                l = mid + 1
        
        if l == len(arr):
            return -1

        return l

    def numMatchingSubseq(self, s: str, words: List[str]) -> int:

        """
        792. 匹配子序列的单词数
        https://leetcode.cn/problems/number-of-matching-subsequences/description/
        :param s:
        :param t:
        :return:
        """
        # 对字符串s进行预处理，将每个字符出现的索引位置按顺序存到数组里
        idx = [[] for _ in range(256)]
        for i, c in enumerate(s):
            idx[ord(c)].append(i)

        res = 0
        for word in words:
            # 串s上的指针
            j = 0
            flag = True
            for i, c in enumerate(word):
                # 整个s就没有c
                if not idx[ord(c)]:
                    flag = False
                    break
                pos = self.left_bound(idx[ord(c)], j)
                # 二分查找没有找到字符c
                if pos == -1:
                    flag = False
                    break
                # 向前移动指针j
                j = idx[ord(c)][pos] + 1

            if flag:
                res += 1

        return res

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111