0%

### 题目描述

Given a string s and a string t, check if s is subsequence of t.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, `"ace"` is a subsequence of `"abcde"` while `"aec"` is not).

### 例子

#### 例子 1

Input: s = “abc”, t = “ahbgdc”
Output: true

#### 例子 2

Input: s = “axc”, t = “ahbgdc”
Output: false

If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

### 解题思路

• `i == 0`：此时相当于 `s` 为空串，是任何字符串的子序列，所以 `isSubseq[0][~] = true`
• `i > 0 && j == 0`，此时 `s` 的长度比 `t` 长，`isSubseq[i][0] = false`

• `isSubseq[i][j - 1] = true`，意味着 `s` 的前 `i` 位是 `t` 的前 `j - 1` 位的子序列，所以肯定也是`t` 的前 `j` 位的子序列， `isSubseq[i][j] = true`
• 否则则判断两个字符串当前位置是否相等，且前一位是否为对方的子序列，即： `s[i-1] == t[j-1] && isSubseq[i - 1][j - 1]`

• 时间复杂度: O(mn)
• 空间复杂度: O(mn)

GitHub 代码同步地址： 392.IsSubsequence.cpp

GitHub: Leetcode-C++-Solution