代码随想录算法训练营第四十五天 | leetcode：判断子序列,不同的子序列

_zzh 的个人博客 / 15 / 0 / 创建于 1个月前 / 更新于 1个月前

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];
    }
}