0%

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

题目描述

题目链接:392. Is Subsequence

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

Follow Up

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?

解题思路

这道题可以用动态规划的思路来做,维护一个二位数组 isSubseq[len(s)][len(t)],其中 isSubseq[i][j] 表示 s 的前 i 位是不是 t 的前 j 位的子序列。我们需要的结果即为:isSubseq[len(s)][len()t]

首先有两种特殊情况:

  • 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]

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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[0][j] = true;
for (int i = 1; i <= n1; i++) isSubseq[i][0] = 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

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions