【代码随想录-动态规划】T392.判断子序列

T392、判断子序列(6/23)

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/is-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题目跟求解最长子序列思路一样，我按照最长子序列的代码提交了一次，结果正确。
后来参考代码随想录思路，发现一个位置有差异，就是当

s.charAt(i) != s.charAt(j)

这种情况下，我们就不能像原先最长子序列那样求 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

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

因为这个时候 S 的子串[0:i-1] 已经不在 T[0:j-1] 中，所以此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];

dp

public boolean isSubsequence(String s, String t) {
    
        int n = s.length();
        int m = t.length();
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i <= n; i++){
    
            for(int j = 1; j <= m; 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];
                }
            }
        }
        return dp[n][m] == s.length()? true:false;
    }

双指针法

public boolean isSubsequence(String s, String t) {
    
        int n = s.length();
        int m = t.length();
        int i = 0, j =0;
        while(i < n && j < m){
    
            if(s.charAt(i) == t.charAt(j)){
    
                i++;
            }
            j++;
        }
        return i == n?true:false;
    }