代码随想录算法训练营第五十四天 | LeetCode 392. 判断子序列、115. 不同的子序列
1. LeetCode 392. 判断子序列
1.1 思路
- 本题是给两个字符串让我们判断字符串 s 是不是字符串 t 的子序列。子序列要求不能改变数组顺序，不要求连续，其实这题和1143. 最长公共子序列是一样的，本题中如果两个字符串的最长公共子序列长度是字符串 s 的长度的话，那么字符串 s 就应该是字符串 t 的子序列了。本题也算是编辑距离的入门题
- dp 数组及其下标的含义：用一个二维数组就可以表示出两个字符串里每一个元素它的是否相同的情况，dp[i][j]：以 i-1 为结尾的字符串 s 和以 j-1 为结尾的字符串 t 的相同子序列的长度为 dp[i][j]，如果这个长度就是字符串 s 的长度，那字符串 s 就是字符串 t 的子序列。这里定义 i-1 和 j-1 是为了避免对第一行和列进行复杂的初始化，定义为 i 和 j 也行，就是麻烦些
- 递推公式：有两个情况，判断的就是两个元素是否相同。if（s[i-1]==t[j-1]）为什么判断的是 i-1 和 j-1，因为我们 dp 数组就是这么定义的。如果相等 dp[i][j]=dp[i-1][j-1]+1，含义就是这两个元素相等了，就在前面的基础上加 1。如果不相等 else 只能在 t 中删除元素，即如果 s 的 i-1 位置和 t 的 j-1 位置不相等了，就把 t 的 j-1 位置删除掉了，考虑的就是 t 的 j-2 前面的字符串和 s 的 i-1 前面的字符串的相同子序列长度了，也就是 dp[i][j-1]，dp[i][j]=dp[i][j-1]，其实可以理解为继承的意思
- dp 数组的初始化：根据递推公式可以看出推导方向，根据这个推导方向，就需要初始化第一行 dp[0][j] 和第一列 dp[i][0]，根据 dp 数组的含义，这里是 0 的话是需要以 -1 为结尾的相同子序列也就是空串的相同子序列长度，也就是 0 了，因此 dp[i][0]=dp[0][j]=0，其余下标根据递推公式会被覆盖的，因此可以不管，默认为 0 即可
- 遍历顺序：根据推导方向，一定要从左到右从上到下，避免赋的是空值 for（int i=1；i<=s.length()；i++）for（int j=1；j<=t.length()；j++）为什么从 1 开始，因为 0 已经初始化了。为什么要取等于号，因为 dp 数组是从 i-1 和 j-1 开始，不取等于号会漏了最后一个状态，而我们最初定义 dp 数组会是 [s.length()+1][t.length()+1]。最终结果是在 dp[s.length()][t.length()]，如果和 s.length()相等就是 true，反之 false
- 打印 dp 数组：用于 debug
1.2 代码
class Solution { public boolean isSubsequence(String s, String t) { int length1 = s.length(); int length2 = t.length(); int[][] dp = new int[length1+1][length2+1]; for(int i = 1; i <= length1; i++){ for(int j = 1; j <= length2; 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[length1][length2] == length1){ return true; }else{ return false; } } }
2. LeetCode 115. 不同的子序列
2.1 思路
- 本题求的是子序列，不要求连续，问的是 s 有多少个 t 这样的子序列，其实就是相当于问 s 可以有多少种删除元素的方式。
- dp 数组及其下标的含义：对于两个字符串比较里面的元素是否相同的情况是定义二维数组，dp[i][j]：以 i-1 为结尾的 s 中有以 j-1 为结尾的 t 的个数为 dp[i][j]。为什么定义 i-1 和 j-1 上面解释过了
- 递推公式：if（s[i-1]==t[j-1]）为什么判断的是 i-1 和 j-1，看看 dp 数组的含义，如果相等就不需要考虑这两个字母，而是 i-2 和 j-2 为结尾的个数即 dp[i-1][j-1]，那也可以考虑不使用 s[i-1]，为什么呢？举例：s=bagg，t=bag，如果不使用 s[3] 此时前面的也可以等于 t，这种情况不使用它就相当于把 s[i-1] 删除掉了，此时的情况就是 dp[i-1][j]。而我们这里不求 t 有多少个 s，因此不能不考虑 t[j-1]。那因此 dp[i][j] 就应该是考虑 s[i-1] 和不考虑 s[i-1] 的情况相加，dp[i][j]=dp[i-1][j-1]+dp[i-1][j]。如果 s[i-1]!=t[j-1] 就是把 s[i-1] 删除的情况，就是不考虑它了，就 dp[i][j]=dp[i-1][j]。
- dp 数组的初始化：根据递推公式可以看出推导方向，因此最上方的第一行和第一列一定要初始化，dp[0][j] 第一行这种情况就是以-1 为结尾的空字符串 s 有以 j-1 为结尾的 t 的个数，空字符串肯定没有 t，因此初始化为 0；dp[i][0] 第一列这种情况就是以 i-1 为结尾的 s 有以-1 为结尾的空字符串 t 的个数，那就应该是 1 了，s 肯定有一个空字符串，因此初始化为 1，而 dp[0][0] 也就是这种情况了，也初始化为 1
- 遍历顺序：根据推导方向从左到右从上到下，因此 for（int i=1；i<=s.length()；i++）for（int j=1；j<=t.length()；j++），为什么取 1 以及为什么要等于号上面解释过了。最终结果是在 dp[s.length()][t.length()]
- 打印 dp 数组：用于 debug
2.2 代码
class Solution { public int numDistinct(String s, String t) { int[][] dp = new int[s.length() + 1][t.length() + 1]; for (int i = 0; i < s.length() + 1; i++) { dp[i][0] = 1; } for (int i = 1; i < s.length() + 1; i++) { for (int j = 1; j < t.length() + 1; 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[s.length()][t.length()]; } }
