代码随想录笔记_动态规划_392判断子序列

代码随想录二刷笔记记录

LC392.判断子序列

---

题目

子序列问题

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

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

示例 1：

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

示例 2：

输入：s = “axc”, t = “ahbgdc”
输出：false

提示：

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

---

思路分析

思路：

思路：本题思路与LC1143一样，都是判断字符串A是否是字符串B的子串。即子序列问题，易想动态规划。当然，本题也可以使用双指针。

动态规划五部曲

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

dp[i][j] : 表示长度为 [0,i-1] 的 s 和长度为 [0,j-1] 的 t 的最长公共子序列 dp[i][j]
这里需要增维一行一列，为了方便计算。
1
2

2.确定递推公式

s 的第 i-1 个字符和 t 的第 j-1 个字符相等时:

dp[i][j] = dp[i-1][j-1] + 1
1

s的第 i-1 个字符和 t 的第 j-1 个字符不相等时，从s[i-1,j-2],t[i-2,j-1]中取目前最长子序列的长度

dp[i][j] = Max(dp[i-1][j],dp[i][j-1]);
1

但这里可以优化，因为我们只需要判断是否存在子串，返回值为 boolean。因此，只需要最终的dp数组结果即可，不用更新列。具体见5.推演分析，这里先给出更新后的递推公式

dp[i][j] = dp[i][j-1]
1

3.初始化

因为 dp[i][0] 和 dp[0][j] 都是没有意义的,赋值为0即可
本题返回值为boolean，因此二维数组初始化为 0即可。

4.遍历顺序

根据递推公式可知，从前往后遍历

for (int i = 1; i <= lenA; i++) {
    for (int j = 1; j <= lenB; j++) {
         if (s.charAt(i-1) == t.charAt(j-1)){
            dp[i][j] = dp[i-1][j-1] + 1;
         }else {
            dp[i][j] = dp[i][j-1];
         }
     }
}
1
2
3
4
5
6
7
8
9

5.推演分析

以 s = “abc”, t = “ahbgdc” 为例

沿用 LC1143 的方法，进行推演分析，同时更新行列，则有

根据本题只需要更新行，不需要更新列的情况，推演后得

---

代码实现

完整代码实现

public boolean isSubsequence(String s, String t) {
        int lenA = s.length();
        int lenB = t.length();
        //初始化
        int[][] dp = new int[lenA + 1][lenB + 1];
        //遍历
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                if (s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    //推演1的实现
//                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                    //推演2
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if (dp[lenA][lenB] == lenA){
            return true;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---