[数据结构与算法]leetcode 392 判断子序列

前言

题目：392. 判断子序列

参考题解：判断子序列-代码随想录

提交代码

双指针

看到这道题目的时候，标签为简单。嘿嘿，应该没啥花里胡哨的，直接按照逻辑解，应该就可以。

代码如下。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        // 贪心：按照s中字母出现的顺序，遍历t即可。
        // 贪心证明：同一个字母，早出现，包含晚出现
        int index = 0;
        bool flag = true;
        for(int i=0; i<s.size(); i++){
            bool find = false;
            for(index; index<t.size(); index++){
                if(t[index] == s[i]){
                    find = true;
                    index++;
                    break;
                }
            }
            if(find == false){
                flag = false;
                break;
            }
        }
        return flag;
    }
};

题解使用双指针的方法，实现上面的思路，代码比较简洁。下面代码，来自参考题解。

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

动态规划

因为刚做过leetcode 1143 最长公共子序列。所以很容易联想到，使用最长公共子序列来解决这道题目。代码如下。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        // 动态规划:dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度
        // 求s和t的最长公共子序列长度。如果这个长度等于s的长度，说明s是t的子序列
        int len1 = s.size();
        int len2 = t.size();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));

        for(int i=1; i<=len1; i++){
            for(int j=1; j<=len2; j++){
                if(s[i-1] == t[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }

        for(auto vec : dp){
            for(auto v : vec)
                cout<<v<<" ";
            cout<<endl;
        }

        return dp[len1][len2] == len1 ? true:false;
    }
};

参考题解，对上面动态规划，进行了优化。可以优化的原因，当比较到s[i]的时候，s[i-1]必然匹配到。(有点意思，相当于要求s连续，t可以不连续)

if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];

下面代码，来自参考题解。

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;
    }
};