LeetCode 392 判断子序列

392.判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

进阶：

如果有大量输入的 S ，称作 S1, S2, ... , Sk 其中 k >= 10亿 ，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例：

输入：s = “abc”, t = “ahbgdc”
输出：true

双指针法

使用两个指针 i,j 分别指向串 s 和串 t ，s[i]==t[j],i++,j++ 否则 j++ 当 i=s.size() 时，说明是子序列，否则移动到 j=t.size() 结束。

代码实现：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n=s.size(),m=t.size(),i=0,j=0;
        for(;i<n,j<m;j++){
            if(s[i]==t[j]) i++;
        }
        if(i==n) return true;
        return false;
    }
};

动态规划

此处使用动态规划主要是处理进阶问题，当有多个子序列 s 需要进行判断时，那么就需要使用一个动态规划数组做相应的记录处理。（本题并不适合使用动规进行求解，但确实可以套用相应的思想）

1. 动态规划数组的定义：定义动态规划数组 dp[i][j] 表示以下标 i-1 为结尾的字符串 s ，和以下标 j-1 为结尾的字符串 t ，相同子序列的长度为 dp[i][j] 。
2. 动态规划数组的推导：（本质思想还是和双指针的求解方式相同）对于 s[i-1]==t[j-1] 说明此时相同子序列的长度可以加一， dp[i][j]=dp[i-1][j-1]+1 。当 s[i-1]!=t[j-1] 时，子序列的长度不能增加，那么 dp[i][j] = dp[i][j-1]
3. 动态规划数组的初始化：将第一行第一列初始化为0即可，因为初始时不存在元素。
4. 动态规划数组的遍历顺序：逐行遍历，从前向后

代码实现：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= t.size(); j++) {
                if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = dp[i][j - 1];
            }
        }
        if (dp[s.size()][t.size()] == s.size()) return true;
        return false;
    }
};