> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/er-fen/392-pan-duan-zi-xu-lie.md).

# \[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)])
```