代码随想录训练营Day55| 392.判断子序列 ；115.不同的子序列

 392.判断子序列 

class Solution {public boolean isSubsequence(String s, String t) {int m = s.length();int n= t.length();if(m>n) return false;int[][] dp = new int[m+1][n+1];dp[0][0]=0;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s.charAt(i-1)==t.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i][j-1], dp[i-1][j]);}}}return dp[m][n]==m;}
}

 

 115.不同的子序列  

class Solution {public int numDistinct(String s, String t) {int m = s.length();int n = t.length();int[][] dp =new int[m+1][n+1];for(int i=0;i<=m;i++){dp[i][0] = 1;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s.charAt(i-1)==t.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}else{dp[i][j] = dp[i-1][j];}}}return dp[m][n];}
}