题目描述

题目链接：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]

代码如下：

#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