代码随想录算法训练营第55天 |392.判断子序列、115.不同的子序列

发布于 2023-03-30  986 次阅读

AI 摘要

本文讲解了 LeetCode 上两道字符串相关的算法题目：392. 判断子序列和115. 不同的子序列的解题思路和代码实现。对于第一道题，本文提供了两种解法，分别是双指针法和动态规划法，并给出了标准答案的代码。对于第二道题，本文详细介绍了使用动态规划求解该问题的方法。其中，根据动态规划的思想，详细描述了如何确定 dp 数组的含义、递推公式、初始化方式和遍历顺序等问题，并给出了 AC 代码。

392. 判断子序列 - 力扣（Leetcode）

思路:

  • 使用动态规划

    1. 确定dp数组以及下标的含义

      • dp[i][j]的定义为：s[i - 1]结尾和t[j - 1]结尾的最长公共子序列长度

    2. 确定递推公式

      // 状态转移方程
if(s[i - 1] == t[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
    dp[i][j] = dp[i][j - 1];
}

    3. dp数组如何初始化

      vector< vector<int> > dp(s.size() + 1, vector<int>(t.size() + 1, 0));

    4. 确定遍历顺序

      从 i = 1 和 j = 1 开始

我的AC代码

双指针法

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int cur = 0;
        for(int i = 0; i < t.size(); ++i) {
            if(s[cur] == t[i]) {
                cur++;
            }
        }
        if(cur == s.size()) {
            return true;
        }
        return false;
    }
};

动态规划

// 时间复杂度O(n x m),空间复杂度O(n x m)
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int cur = 0;
        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;
    }
};

标准答案

// 时间复杂度O(n x m),空间复杂度O(n x m)
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;
    }
};

115. 不同的子序列 - 力扣（Leetcode）

思路:

  • 使用动态规划

    1. 确定dp数组以及下标的含义

      • dp[i][j]的定义为：以s[i - 1]为结尾的字符串的子序列能构成以t[j - 1]为结尾的字符串的数量

    2. 确定递推公式

      // 状态转移方程
for(int j = 1; j <= t.size(); ++j) {
  // 当相等的时候需要考虑两种操作，一种是保留s[i - 1]时
  // 剩下的字符串的子序列与以t[i - 1]为结尾的字符串的匹配情况
  // 还有一种是不考虑s[i - 1]，即把s[i - 1]删去时
  // 剩下的字符串的子序列与以t[i - 1]为结尾的字符串的匹配情况
    if(s[i - 1] == t[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    }
    else {
   // 当不相等的时候，只考虑删去s[i - 1]时的匹配情况
        dp[i][j] = dp[i - 1][j];
    }
}

    3. dp数组如何初始化

      // 从递推公式可知，dp[i][j]是根据左上方和上方匹配出来的
// 所以dp[i][0]要初始化为1(意思是s无论怎么删除都可以构成t)
// dp[0][j]初始化为0(意思是s无论如何都无法构成t)
// dp[0][0]要初始化为1(为了递推的顺利进行，所以认为dp[0][0]是1)
vector< vector<uint64_t> > dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));
dp[0][0] = 1;
for(int i = 0; i <= s.size(); ++i) {
    dp[i][0] = 1;
}

    4. 确定遍历顺序

      从 i = 1 和 j = 1 开始从前往后遍历

我的AC代码

// 时间复杂度O(n x m),空间复杂度O(n x m)
class Solution {
public:
    int numDistinct(string s, string t) {
        vector< vector<uint64_t> > dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));
        dp[0][0] = 1;
        for(int i = 0; i <= s.size(); ++i) {
            dp[i][0] = 1;
        }
        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] + dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.size()][t.size()];
    }
};

标准答案

// 时间复杂度O(n x m),空间复杂度O(n x m)
class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
        for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
        for (int j = 1; j < t.size(); j++) dp[0][j] = 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] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.size()][t.size()];
    }
};