## [Leetcode]392. Is Subsequence(C++)

### 题目描述

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[~] = true`
• `i > 0 && j == 0`，此时 `s` 的长度比 `t` 长，`isSubseq[i] = 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]`

``````#include <string>
#include <vector>

class Solution {
public:
bool isSubsequence(std::string s, std::string t) {
int n1 = s.length(), n2 = t.length();

// isSubseq[i][k] indicates whether s[0::i] is subsequence of t[0::j]
std::vector<std::vector<bool>> isSubseq(n1 + 1, std::vector<bool>(n2 + 1, false));

for (int j = 0; j <= n2; j++) isSubseq[j] = true;
for (int i = 1; i <= n1; i++) isSubseq[i] = false;

for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (isSubseq[i][j - 1]) {
// if s is already a subsequence of t, it must be subsequence of t + any letter
isSubseq[i][j] = true;
} else {
isSubseq[i][j] = (s[i-1] == t[j-1]) && isSubseq[i - 1][j - 1];
}
}
}

return isSubseq[n1][n2];
}
};
``````
• 时间复杂度: O(mn)
• 空间复杂度: O(mn)

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

Built with Hugo
Theme Stack designed by Jimmy