代码随想录算法训练营第四十五天 | leetcode：判断子序列,不同的子序列
2 / 0 / 创建于 10个月前 /
_zzh 的个人博客
392. 判断子序列
解题方法
- dp数组的含义：dp[i][j]：表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
- 确定递推公式：主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
- 情况1：if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1
因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1.- 情况2：if (s[i - 1] != t[j - 1]) dp[i][j] = dp[i][j - 1]
此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了。- 初始化dp数组：从递推公式可以看出，dp[i][0] 表示以下标i-1为结尾的字符串，与空字符串的相同子序列长度，所以初始化为0。 dp[0][j]同理。其余值由初始化值可以推出覆盖，所以初始化多少都可以。统一初始化为0。
- 遍历顺序：从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右
code
class Solution {
/**
* @param String $s
* @param String $t
* @return Boolean
*/
function isSubsequence($s, $t) {
$len1 = strlen($s);
$len2 = strlen($t);
$dp = array_fill(0, $len1+1, array_fill(0, $len2+1, 0));
//print_r($dp);
for($i = 1; $i <= $len1; $i++){
for($j = 1; $j <= $len2; $j++){
if($s[$i-1] == $t[$j-1]){
$dp[$i][$j] = $dp[$i-1][$j-1] + 1;
}else{
//这里不需要$dp[$i-1][$j]是因为s不用做裁剪，始终以s与t比较
$dp[$i][$j] = $dp[$i][$j-1];
}
}
}
//print_r($dp);
//判断两个公共子序列长度是否等于s的长度
return $dp[$len1][$len2] == $len1;
}
}复杂度
时间复杂度
O(n x m)其中 n 和 m 分别为 text1 和 text2 的长度
空间复杂度
O(n x m)
双指针
class Solution {
/**
* @param String $s
* @param String $t
* @return Boolean
*/
function isSubsequence($s, $t) {
$tLen=strlen($t);
$sLen=strlen($s);
$j=0;
for($i=0;$i < $tLen;$i++){
//判断s与t相等的元素
if($s[$j]==$t[$i]){
//慢指针移动
$j++;
}
}
return $j==$sLen;//判断j和s的长度
}
}复杂度
时间复杂度
O(n)
空间复杂度
O(1)
115. 不同的子序列
解题方法
- dp数组的含义：dp[i][j] ：表示以i-1结尾的s中有以j-1结尾的t的个数为dp[i][j]
- 确定递推公式：
- 情况1：if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。例如：s为 “bagg” ， t为 “bag” 时，有以下两种情况
- 一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。
- 一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。
- 情况2：if (s[i - 1] != t[j - 1]) dp[i][j] = dp[i-1][j]
当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素）- 初始化dp数组：
- dp[i][0] = 1 因为s中可以删除所有元素变为空字符串
- dp[0][j] = 1 因为s为空不能变为不为空的t.
- dp[0][0] = 1 因为s为空, t为空,相等
- 其余初始化为0.
- 遍历顺序：递推公式中dp[i][j]依赖于[i - 1][j - 1]的状态，所以遍历顺序从上到下，从左到右。
code
class Solution {
/**
* @param String $s
* @param String $t
* @return Integer
*/
function numDistinct($s, $t) {
$sLen = strlen($s);
$tLen = strlen($t);
$dp = array_fill(0, $sLen + 1 , array_fill(0, $tLen + 1, 0));
for($i=0; $i<=$sLen;$i++) $dp[$i][0] = 1;
for($j=1; $j<=$tLen;$j++) $dp[0][$j] = 0;
for($i = 1; $i<=$sLen; $i++){
for($j=1; $j<=$tLen;$j++){
if($s[$i-1] == $t[$j-1]){
//s为bagg时 t为bag时 有以下两种情况
$dp[$i][$j] = $dp[$i-1][$j-1] + $dp[$i-1][$j];
}else{
$dp[$i][$j] = $dp[$i-1][$j];
}
}
}
//print_r($dp);
return $dp[$sLen][$tLen];
}
}复杂度
时间复杂度
O(n * m)
空间复杂度
O(n * m)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号