Day54題目

LeetCode392判斷子序列

核心思想:公共子序列長度達到需要判斷的字符串的長度,說明是子序列

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

LeetCode115.不同的子序列

核心思想:dp[i][j] 表示s前i個字符中包含t前j個字符序列的個數(shù)

class Solution {public int numDistinct(String s, String t) {int[][] dp = new int[s.length()+1][t.length()+1];// 初始化i 0 為1 ,s為1個字符,t為空的時候,只要刪除這個字符就能得到t,所以是1for(int i = 0 ; i <= s.length(); i ++) dp[i][0]=1;for(int i = 1 ; i <= s.length() ; i ++){for(int j = 1 ; j <= t.length(); j ++){// 相同的時候,是左上角和左邊(不使用當前的s字符)的個數(shù)的和if(s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}else{// 否則的話就是和不使用s 當前字符的數(shù)量一樣多dp[i][j] = dp[i-1][j];}}}return dp[s.length()][t.length()];}
}