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

Created 5 years ago by 吴亲库里, Updated 5 years ago Revision #1 2300 views 0 likes 0 collects

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

题目描述

这道题有点意思的。给定两个字符串，要你在字符串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;
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php