[code Capriccio - dynamic planning] t392 Judgement subsequence

T392、 Judging subsequences (6/23)

Given string s and t , Judge s Is it t The subsequence .
A subsequence of the string is the original string delete some （ It can also be done without deleting ） A new string of characters formed without changing the relative positions of the remaining characters .（ for example ,"ace" yes "abcde" A subsequence of , and "aec" No ）.
Advanced ：
If there is a lot of input S, Referred to as S1, S2, … , Sk among k >= 10 Billion , You need to check in turn whether they are T The subsequence . under these circumstances , How would you change the code ？
source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/is-subsequence
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

This problem is the same as solving the longest subsequence , I submitted once according to the code of the longest subsequence , Results the correct .
Later reference code Capriccio ideas , Found a location difference , Is that when

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

In this case , We can't solve the problem like the original longest subsequence dp[i][j] = max(dp[i-1][j], dp[i][j-1])

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

Because at this time S The string of [0:i-1] No longer T[0:j-1] in , So this is equivalent to t To delete an element ,t If the current element t[j - 1] Delete , that dp[i][j] And the value of that is see s[i - 1] And t[j - 2] The comparison results of , namely ：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;
    }

Double finger needling

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;
    }