【动态规划】 392. 判断子序列

8 392. 判断子序列

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

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

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

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

简单问题简单做

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s == null || s.length() == 0) {
            return true;
        }
        if(s.length() > t.length()) {
            return false;
        }
        var i = 0;
        var j = 0;
        for(i = 0; i < s.length(); i++) {
            while(j < t.length() 
                    && s.charAt(i) != t.charAt(j)) {
                j++;
            }
            if(i == s.length() - 1 && j < t.length()) {
                return true;
            }
            j++;
        }
        return false;
    }
}

​ 甚至直接使用函数库

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s == null || s.length() == 0) {
            return true;
        }
        var index = -1;
        for(var i = 0; i < s.length(); i++) {
            index = t.indexOf(s.charAt(i), index + 1);
            if(index == -1) {
                return false;
            }
        }
        return true;
    }
}

千万不能有上面的想法：尝试动态规划

​ 第一种dp[I][J]定义：s下标为i的子序列是否是和t下标j前的子序列的子序列

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s == null || s.length() == 0) {
            return true;
        }
        if(t == null || t.length() < s.length()) {
            return false;
        }
        var len1 = s.length();
        var len2 = t.length();
        var dp = new boolean[len1+1][len2+1];

        for(var i = 1; i <= len1; i++) {
            for(var j = 1; j <= len2; j++) {
                dp[i][j] = dp[i][j-1];
                if(!dp[i][j] && s.charAt(i-1) == t.charAt(j-1)) {
                    if(i == 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }

        for(var item : dp) {
            System.out.println(Arrays.toString(item));
        }

        return dp[len1][len2];
    }
}

​ 一维数组优化：

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s == null || s.length() == 0) {
            return true;
        }
        if(t == null || t.length() < s.length()) {
            return false;
        }
        var len1 = s.length();
        var len2 = t.length();
        var dp = new boolean[len2+1];

        for(var i = 1; i <= len1; i++) {
            var pre = false;
            // 思考为什么是正序
            for(var j = 1; j <= len2; j++) {
                var cur = dp[j];
                dp[j] = dp[j-1];
                if(!dp[j] && s.charAt(i-1) == t.charAt(j-1)) {
                    if(i == 1) {
                        dp[j] = true;
                    } else {
                        dp[j] = pre;
                    }
                }
                pre = cur;
            }
        }

        // for(var item : dp) {
        //     System.out.println(Arrays.toString(item));
        // }

        return dp[len2];
    }
}

​ 第二种dp定义，dp[i][j]表示s的下标i的子串和t的下标j的子串重复的长度，从题解看到的：

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s == null || s.length() == 0) {
            return true;
        }
        if(t == null || t.length() < s.length()) {
            return false;
        }
        var len1 = s.length();
        var len2 = t.length();

        var dp = new int[len1+1][len2+1];

        for(var i = 1; i <= len1; i++) {
            for(var j = 1; j <= len2; j++) {
                dp[i][j] = dp[i][j-1];
                if(s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + 1);
                }
            }
        }

        return dp[len1][len2] == len1;
    }
}

​ 一维数组优化：

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s == null || s.length() == 0) {
            return true;
        }
        if(t == null || t.length() < s.length()) {
            return false;
        }
        var len1 = s.length();
        var len2 = t.length();

        var dp = new int[len2+1];

        for(var i = 1; i <= len1; i++) {
            var pre = 0;
            for(var j = 1; j <= len2; j++) {
                var cur = dp[j];
                dp[j] = dp[j-1];
                if(s.charAt(i-1) == t.charAt(j-1)) {
                    dp[j] = Math.max(dp[j], pre + 1);
                }
                pre = cur;
            }
        }

        return dp[len2] == len1;
    }
}