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

发布于 2023-03-30  1,396 次阅读


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()];
    }
};