代码随想录算法训练营第五十八天

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

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

视频讲解https://www.bilibili.com/video/BV1tv4y1B7ym/?spm_id_from=333.788&vd_source=f98f2942b3c4cafea8907a325fc56a48 文章讲解https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html

思路：
- dp数组含义：
  - dp[i][j]：s的子串[0, i - 1] 与 t的子串[0, j - 1] 的最长公共子序列的长度
- 递推公式：
  - 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];
  - 注意与LeetCode 1143.最长公共子序列的区别：
    1143如果text1[i - 1]与text2[j - 1]不匹配可以：
    1. text1删末位与 text2👉dp[i -1][j]
    2. text1 与 text2删末位👉dp[i][j - 1]
  - 本题只用维护 s 与 t删末位👉dp[i][j - 1]维护 s删末位与 t 没有意义反正是false
- 初始化：全0
  - s[0, i-1]和空串的最长公共子序列是0👉dp[i][0] = 0
  - 同理dp[0][j] = 0
- 遍历顺序：从上到下从左到右
- 最终结果：dp[text1.size()][text2.size()] == s.size()
代码：

// 动态规划：
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;
    }
};
// 时间复杂度：O(n × m)
// 空间复杂度：O(n × m)

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

LeetCode 115.不同的子序列