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

## 题目描述

[392. 判断子序列](https://leetcode-cn.com/problems/is-subsequence/) [792. 匹配子序列的单词数](https://leetcode-cn.com/problems/number-of-matching-subsequences/)

给定字符串 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`已经越界, 说明没有满足的字符, 即不匹配.

图解逻辑可参考: [二分查找高效判定子序列](https://labuladong.gitbook.io/algo/gao-pin-mian-shi-xi-lie/er-fen-cha-zhao-pan-ding-zi-xu-lie)

```python
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
```

后续挑战的答案:

```python
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)])
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/er-fen/392-pan-duan-zi-xu-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.