392.判断子序列
题目链接：力扣
思路
比较简单的思路就是使用双指针来判断子序列，这里主要使用动态规划，是编辑距离的入门题目
1、确定dp数组
dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
2、确定递推公式
有两种情况：
if (s[i - 1] == t[j - 1])
t中找到了一个字符在s中也出现了。dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1
if (s[i - 1] != t[j - 1])
此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];
动态动画推导视频推荐：判断子序列
3、初始化dp数组
从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的
4、遍历顺序
从前向后进行遍历
判断子序列
动态规划
class Solution { public boolean isSubsequence(String s, String t) { int slen = s.length(); int tlen = t.length(); // 创建dp数组 int[][] dp = new int[slen+1][tlen+1]; // 推导dp数组 for (int i = 1; i <= slen; i++) { for (int j = 1; j <= tlen; 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[slen][tlen] == slen) { return true; } else { return false; } } }
双指针
class Solution { public boolean isSubsequence(String s, String t) { int sindex = 0; int tindex = 0; while (sindex < s.length() && tindex < t.length()) { if (s.charAt(sindex) == t.charAt(tindex)) { sindex++; } tindex++; } return sindex == s.length(); } }
115.不同的子序列
题目链接：力扣
思路
反正不是很好理解，再多看几次吧
1、确定dp数组
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
2、确定递推公式
有两种情况：
s[i - 1] 与 t[j - 1]相等
当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成
dp[i][j] = dp[i - 1][j]
3、初始化dp数组
根据递推公式，要初始化dp[i][0] 和 dp[0][j]，以及特殊的dp[0][0]
dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数，所以都是1
dp[0][j] 表示：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数，所以都是0
dp[0][0] 应该是1，空字符串s，可以删除0个元素，变成空字符串t
4、遍历顺序
从上到下，从左到右
不同的子序列
class Solution { public int numDistinct(String s, String t) { int slen = s.length(); int tlen = t.length(); // 创建dp数组 int[][] dp = new int[slen+1][tlen+1]; // 初始化dp数组 for (int i = 0; i < slen + 1; i++) { dp[i][0] = 1; } for (int i = 1; i <= slen; i++) { for (int j = 1; j <= tlen; 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[slen][tlen]; } }
