算法随想录算法训练营第四十五天|392.判断子序列 115.不同的子序列

392.判断子序列 

题目：给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

class Solution {public boolean isSubsequence(String s, String t) {if(s.length() == 0)return true;char[] s1 = s.toCharArray();char[] t1 = t.toCharArray();int index = 0;for(int i = 0;i<t.length();i++){if(s1[index] == t1[i]){index++;}if(index>=s.length())break;}return index >= s.length()?true:false;}
}

115.不同的子序列  

题目：给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

思路：首先定义一个二维数组，我认为动态规划的题是关键点需要明白dp[i][j] 代表什么，这题的dp[i][j] 代表着 t 字符串的前 i 个字符可以由 s 字符串的前 j 字符组成的最多个数。

第一种情况：t 字符串下标为 i 所对应的字符等于 s 字符下标为 j 所对应的字符时：

① 使用新加入的 j 所对应的字符匹配，方案有 dp[i-1][j-1] 种（我认为可以理解为01背包中取物品的情况）

② 不使用新加入的 j 所对应的字符匹配，方案有 dp[i][j-1] 中（可以理解为01背包中取物品的情况）

即 dp[i][j] = dp[i-1][j-1]+dp[i][j-1];

第二种情况：t 字符串下标为 i 所对应的字符不等于 s 字符下标为 j 所对应的字符时，此时

 dp[i][j] = dp[i][j-1];

class Solution {public int numDistinct(String s, String t) {int len1 = t.length();int len2 = s.length();int[][] dp = new int[len1+1][len2+1];for(int i = 0;i<len2;i++){dp[0][i] = 1; }for(int i = 1;i<=len1;i++){for(int j = 1;j<=len2;j++){if(t.charAt(i-1) == s.charAt(j-1)){dp[i][j] = dp[i-1][j-1]+dp[i][j-1];//dp[i-1][j-1] 取的情况，dp[i][j] 不取的情况}else{dp[i][j] = dp[i][j-1]; }}}return dp[len1][len2];}
}