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

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