Leetcode基础刷题之PHP解析( 115. Distinct Subsequences)

做这道题的时候可以看看之前关于动态规划的文章:


8b8c9d8eab377b86b204a6e725989aa6.png


题目描述

这道题有点意思的。给定两个字符串,要你在字符串S中找出所有字符串T的子序列。第一个b太多了,容易弄混,直接看例子2。最终的结果是5,就说明在babgbag中能找出5个bag这样的子序列。你可以中间删除或者不删,T是bag,从S的第一个字符串找,先ba,下一个是b,bab不是他的子序列,在下一个是g,现在S中babg删掉b就是子序列了。就是这样的顺序,可以从中删除掉不符合的字符,但是位置不能对换来比较,最终有五个组合。


题目分析

不是很像爬楼梯的问题吗?就是在求字符串S长度为m时和字符串T长度为n时匹配情况,那么我们就需要求字符串S长度为[m-1]和字符串T长度为[n]-1的匹配情况....那么他的递推方程就是

$dp[$m][$n]=$dp[$m-1][$n]+$dp[$m-1][$n-1]||+0

为什么有可能是加0呢。因为在匹配的过程中如果S[$m-1] !==$t[$n-1],就说明他的上一级S的第m-1和t的n-1位置是不匹配的,用上面的例子通俗的解释这句话就是在babg匹配bag的时候至少有bab匹配bag种情况。还有一点返回的可能会是0,这其实就是边界的问题,因为是在S中找等于T的子序,所以输入值的时候T可以是空值,空值是任意字符串的子序列,S和T也可以同时为空,但是S为空的时候,如果T不为空,那么一定是0。
代码实现   

  /**
     * @param String $s
     * @param String $t
     * @return Integer
     */
    function numDistinct($s, $t) {
        
        $m=strlen($s);
        $n=strlen($t);
        for($i=0;$i<$m;$i++) $dp[$i][0]=1;
                
        for($i=1;$i<=$m;$i++){
            for($j=1;$j<=$n;$j++){
                if($s[$i-1]==$t[$j-1]){
                    $dp[$i][$j] =$dp[$i-1][$j]+$dp[$i-1][$j-1];
                }else{
                    $dp[$i][$j]=$dp[$i-1][$j];
                }
            }
        }
        return $dp[$m][$n]??0;
    }

吴亲库里 has written 98 articles

情绪只是对自己无能的愤怒

积分:4787 等级:P8 职业:php 城市:杭州

3 条回复

  1. moting moting says:

    想请问一下,这道题测试过吗?我在调试的过程中看到 $dp[0][$j] 不存在,$j = 1。

登录后才能进行评论,立即登录?