[392][简单][二分] 判断子序列

题目描述

392. 判断子序列 792. 匹配子序列的单词数

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1:

s = "abc", t = "ahbgdc"
返回 true.

示例 2:

s = "axc", t = "ahbgdc"
返回 false.

后续挑战 :

如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

解题思路

贪心

使用贪心思路, 本题很简单. 从t的第一个字母开始, 逐个遍历寻找s中的字符, 每找到s中的一个字符, 就寻找s中的下一个字符, 直到:

• 遍历完t, 但s还有剩余的字符, 说明不匹配

• s中的每一个字符都在t中找到了对应的字符, 说明匹配

贪心的思路就是对于s中的每个字符, 我们只需要找到t中剩余字符中的最左侧的匹配位置, 因此如果一个偏右的位置匹配, 并最终s和t完全匹配, 那么将这个字符的匹配换成最左侧的位置, s和t肯定也是完全匹配的.

这样能够在$O(N)$的时间复杂度下完成判断.

二分

这里考虑到后续挑战, 要对大量的s, 判断每一个是否匹配, 这样$O(MN)$的时间复杂度就有些慢了. 可以通过二分的方法, 将一个s判断的时间从$O(N)$, 降到$O(\log N)$.

对于一个s, 从s的第一个字符开始, 找每个字符在t中合适的位置. 如果需要判断多个s是否与t匹配, 我们可以先遍历一遍t, 记录每个字符在t中的所有位置. 这是因为对于某个s中的某个字符s[i], 我们在寻找位置时, 只会跟当前这个字符所在的所有位置匹配, 这样就可以使用二分方法来搜索了.

对于s中的每个字符s[i], 我们记录上一个字符s[i - 1]在t中的位置pos(对于s[0]来说, 上一个字符的位置定义为-1), 然后我们要在pos + 1到位置是否在t中这个字符对应的索引列表的范围内, 如果在, 我们要找到不小于pos + 1的第一个位置. 因此, 以pos + 1为目标, 对这个有序的索引列表进行二分搜索, 如果中间位置小于目标就移动left, 否则移动right, 最终left停留的位置, 就是不小于pos + 1的第一个位置, 但如果left已经越界, 说明没有满足的字符, 即不匹配.

图解逻辑可参考: 二分查找高效判定子序列

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        mapping = dict()
        for i, char in enumerate(t):
            if char in mapping:
                mapping[char].append(i)
            else:
                mapping[char] = [i]

        current = -1
        for char in s:
            if char not in mapping:
                return False

            indices = mapping[char]
            target = current + 1
            left, right = 0, len(indices) - 1
            while left <= right:
                mid = (left + right) // 2
                if indices[mid] == target:
                    right = mid - 1
                elif indices[mid] > target:
                    right = mid - 1
                elif indices[mid] < target:
                    left = mid + 1
            if left == len(indices):
                return False
            else:
                current = indices[left]
        return True

后续挑战的答案:

class Solution:
    def single_match(self, s, mapping):
        current = -1
        for char in s:
            if char not in mapping:
                return False

            indices = mapping[char]
            target = current + 1
            left, right = 0, len(indices) - 1
            while left <= right:
                mid = (left + right) // 2
                if indices[mid] == target:
                    right = mid - 1
                elif indices[mid] > target:
                    right = mid - 1
                elif indices[mid] < target:
                    left = mid + 1
            if left == len(indices):
                return False
            else:
                current = indices[left]
        return True

    def numMatchingSubseq(self, S: str, words: List[str]) -> int:
        mapping = dict()
        for i, char in enumerate(S):
            if char in mapping:
                mapping[char].append(i)
            else:
                mapping[char] = [i]

        return len([1 for s in words if self.single_match(s, mapping)])