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

392. 判断子序列

解题方法

  1. dp数组的含义:dp[i][j]:表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]
  2. 确定递推公式:主要就是两大情况: 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]的比较结果了。
  3. 初始化dp数组:从递推公式可以看出,dp[i][0] 表示以下标i-1为结尾的字符串,与空字符串的相同子序列长度,所以初始化为0。 dp[0][j]同理。其余值由初始化值可以推出覆盖,所以初始化多少都可以。统一初始化为0。
  4. 遍历顺序:从递推公式可以看出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. 不同的子序列

解题方法

  1. dp数组的含义:dp[i][j] :表示以i-1结尾的s中有以j-1结尾的t的个数为dp[i][j]
  2. 确定递推公式:
    • 情况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中删除这个元素)
  3. 初始化dp数组:
    • dp[i][0] = 1 因为s中可以删除所有元素变为空字符串
    • dp[0][j] = 1 因为s为空不能变为不为空的t.
    • dp[0][0] = 1 因为s为空, t为空,相等
    • 其余初始化为0.
  4. 遍历顺序:递推公式中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 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!