动态规划求解判断子序列问题

leetcode 题库 392 判断子序列

一、
①
s 中的前 i 个字符是 t 中前 j 个字符的子序列，则 dp[i][j] = true
s 中的前 i 个字符不是 t 中前 j 个字符的子序列，则 dp[i][j] = false

二、
# 1、比较的 s 的第 i 个字符和 t 的第 j 个字符相等

** s 的前 i - 1 项是 t 的前 j - 1 项的子序列**

    s = "abc"
    t = "aebc"
    i = 3
    j = 4
    此时对于字符串 s 和 t 来说，最后两个字符相等
    由于 "ab" 是 "aeb" 的子序列，由 ① 得 dp[2][3] = true
    由于 s 和 t 的最后两个字符相等
    所以 "abc" 是 "aebc" 的子序列，由 ① 的 dp[3][4] = true

** s 的前 i - 1 项不是 t 的前 j - 1 项的子序列**

    s = "adc"
    t = "aebc"
    i = 3
    j = 4
    此时对于字符串 s 和 t 来说,最后两个字符相等
    由于 "ad" 不是 "aeb" 的子序列，由 ① 得 dp[2][3] = false
    即使 s 和 t 的最后两个字符相等
    "adc" 也不是 "aebc" 的子序列，由 ① 的 dp[3][4] = false

# 2、比较的 s 的第 i 个字符和 t 的第 j 个字符不相等

** s 的前 i 项是 t 的前 j - 1 项的子序列**

    s = "ade"
    t = "abdef"
    i = 3
    j = 5
    此时对于字符串 s 和 t 来说,最后两个字符不相等
    由于 "ade" 是 "abde" 的子序列，由 ① 得 dp[3][4] = true
    那么为 t 添加一个不相等的字符之后，"ade" 也是 "abdef" 的子序列，由 ① 得 dp[3][5] = true

** s 的前 i 项不是 t 的前 j - 1 项的子序列**

    s = "ace"
    t = "abdef"
    i = 3
    j = 5
    此时对于字符串 s 和 t 来说,最后两个字符不相等
    由于 "ace" 不是 "abde" 的子序列，由 ① 得 dp[3][4] = false
    那么为 t 添加一个不相等的字符之后 "ade" 也不是 "abdef" 的子序列，由 ① 得 dp[3][5] = false

三、

---

综上所述：

    当最后两个字符相等的时，即 dp[i][j] = dp[i - 1][j - 1]
            当 s 的长度为 i - 1,t 的长度为 j - 1 时
            若 s 为   t 的子序列，则当 s 的长度为 i ,t 的长度为 j 时，s 也为   t 的子序列
            若 s 不为 t 的子序列，则当 s 的长度为 i ,t 的长度为 j 时，s 也不为 t 的子序列
    当最后两个字符串不相等时，即 dp[i][j] = dp[i][j - 1]
            当 s 的长度为 i,t 的长度为 j - 1 时
            若 s 为   t 的子序列，则为 t 则加一个字符之后，s 的长度为 i ,t 的长度为 j 时，s 也为   t 的子序列
            若 s 不为 t 的子序列，则为 t 则加一个字符之后，s 的长度为 i ,t 的长度为 j 时，s 也为   t 的子序列

---

四、

第一步：

初始化：

            将第一行和第一列的数据进行初始化
            第一行表示 t 为空串时，必为 s 的子序列
            第一列表示 s 为空串时，t 必部位 s 的子序列

第二步：

由左到右，由上到下为 dp 数组赋值

            第二行数据：
            dp[1][1] 表示,当 s = "a" t = "a" 时，s 是否为 t 的子序列
            此时两个字符串的最后两个字符相等，所以查看 s="" t = "" (dp[0][0] 表示)时，s 是否为 t 的子序列
            由于 dp[0][0] = true 所以 s = "a" t = "a" 时 s 为 t 的子序列 即 d[1][1] = true

            dp[1][2] 表示,当 s = "a" t = "ah" 时，s 是否为 t 的子序列
            此时两个字符串的最后两个字符不相等，所以查看 s="a" t = "a" (dp[1][1] 表示)时，s 是否为 t 的子序列
            由于 dp[0][0] = true s 为 t 的子序列，为 t 添加一个字符之后 s="a" t = "ah" 此时s 仍为 t 的子序列 即 dp[1][2] = true

            dp[1][3] 表示,当 s = "a" t = "ahb" 时，s 是否为 t 的子序列
            此时两个字符串的最后两个字符不相等，所以查看 s="a" t = "ah" (dp[1][2] 表示)时，s 是否为 t 的子序列
            由于 dp[1][2] = true s 为 t 的子序列，为 t 添加一个字符之后 s="a" t = "ahb" 此时s 仍为 t 的子序列 即 dp[1][3] = true

            dp[1][4],dp[1][5],dp[1][6] 同理

            第三行数据：
            dp[2][1] 表示,当 s = "ab" t = "a" 时，s 是否为 t 的子序列
            此时两个字符串的最后两个字符不相等，所以查看 s="ab" t = "" (dp[2][0] 表示)时，s 是否为 t 的子序列
            由于 dp[2][0] = false s 不为 t 的子序列，为 t 添加一个字符之后 s="ab" t = "a" 此时s 不为 t 的子序列 即 dp[2][1] = false

            dp[2][2] 表示,当 s = "ab" t = "ah" 时，s 是否为 t 的子序列
            此时两个字符串的最后两个字符不相等，所以查看 s="ab" t = "a" (dp[2][1] 表示)时，s 是否为 t 的子序列
            由于 dp[2][1] = false s 不为 t 的子序列，为 t 添加一个字符之后 s="ab" t = "ah" 此时s 不为 t 的子序列 即 dp[2][2] = false

            dp[2][3] 表示 当 s = "ab" t = "ahb" 时，s 是否为 t 的子序列
            此时两个字符串的最后两个字符相等，所以查看 s="a" t = "ah" (dp[1][2] 表示)时，s 是否为 t 的子序列
            由于 dp[1][2] = true s 为 t 的子序列， 当 s="ab" t = "ahb" 此时s 为 t 的子序列 即 dp[2][3] = true
            dp[2][4],dp[2][5],dp[2][6] 同理

            第四行也可以用一样的方法进行求解

五、代码如下

class Solution {
   public boolean isSubsequence(String s, String t) {
        int sLen = s.length(), tLen = t.length();
        if (sLen > tLen) return false;
        if (sLen == 0) return true;
        boolean[][] dp = new boolean[sLen + 1][tLen + 1];
        for (int j = 0; j <= tLen; j++) {
            dp[0][j] = true;
        }

        for (int i = 1; i <= sLen; i++) {
            for (int j = 1; j <= tLen; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[sLen][tLen];
    }
}

打赏