代码随想录35期Day54-Java

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个字符序列的个数

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字符)的个数的和if(s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}else{// 否则的话就是和不使用s 当前字符的数量一样多dp[i][j] = dp[i-1][j];}}}return dp[s.length()][t.length()];}
}