代码随想录day55｜392.判断子序列｜115.不同的子序列｜Golang

代码随想录day55

最后一周啦

392.判断子序列

思路

        当然本题用双指针的思路其实也挺简单的！

        从动态规划的角度来讲，这道题应该算是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。

        所以掌握本题也是对后面要讲解的编辑距离的题目打下基础。

动态规划五部曲分析如下：

1、确定dp数组以及下标的含义

        dp[i][j]表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字t，这两个的相同子序列的长度为dp[i][j]。

        注意这里是判断s是否为t的子序列，即t的长度是大于等于s的。

        有同学问了，为啥要表示下标i-1为结尾的字符串呢？为啥不表示下标i为结尾的字符串呢？主要是统一以i-1为结尾的字符串来计算在下面的递归公式中会容易理解一些，如果还有疑惑，可以先继续往下看。

2、确定递推公式

        在确定递推公式的时候，首先要考虑如下两种操作：

•                if s[i-1] == t[j-1] ，即t中找到了一个字符在s中也出现了。
•                if s[i-1] != t[j-1] ， 相当于t要删除元素，继续匹配

        if s[i-1] == t[j-1]，那么dp[i][j] = dp[i-1][j-1]+1，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1, 如果不理解的话回去看一下dp[i][j]的定义。

        if s[i-1] != t[j-1], 此时相当于t要删除元素，t如果把当前元素t[j-1]删除，俺么dp[i][j]的数值就是 看s[i-1]与t[j-2]的比较结果了，即dp[i][j] = dp[i][j-1]

3、dp数组如何初始化

         从递推公式中可以看出来dp[i][j]都是依赖于dp[i-1][j-1]和dp[i][j-1]的，所以dp[0][0]和dp[i][0]是一定要初始化的。

        这里大家已经可以发现，在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以j-1为结尾的字符串t 他俩相同子序列的长度为dp[i][j].

        因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：

        如果要是定义的dp[i][j]是以下标为i结尾的字符串s和以下标为j结尾的字符串t，那么初始化就麻烦了。

        这里的dp[i][0]和dp[0][j]是没有含义的，仅仅是为了给递推公式做前期铺垫，所以初始化为0。 其实这里只初始化dp[0][j]就足够了，但是一起初始化也方便，所以就一起操作了。

vectorint>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));

4、确定遍历顺序

        同理从递推公式可以看出dp[i][j]都是依赖与dp[i-1][j-1]和dp[i][j-1]的，那么遍历顺序也应该是从上到下，从左到右。如图所示

 5、举例推导dp数组

        以示例一为例，输入：s = "abc", t = "ahbgdc"，dp状态转移图如下：

 

        dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度，所以如果dp[s.size()][t.size()] 与 字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s 就是 t 的子序列。

        图中dp[s.size()][t.size()] = 3， 而s.size() 也为3。所以s是t 的子序列，返回true。

动规五部曲分析完毕，Go代码如下：

func isSubsequence(s string, t string) bool {
    dp := make([][]int,len(s)+1)
    for i:=0;i<len(dp);i++{
        dp[i] = make([]int, len(t)+1)
    }
    for i:=1;i<len(dp);i++{
        for j:=1;j<len(dp[i]);j++{
            if s[i-1] == t[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1 
            } else {
                dp[i][j] = dp[i][j-1] 
            }
        }
    }
    return dp[len(s)][len(t)] == len(s)
}

115.不同的子序列

思路

        这道题目如果不是子序列，而是要求连续序列的，那就可以考虑用KMP。

        这道题目相对于72. 编辑距离，简单了不少，因为本题相当于只有删除操作，不用考虑替换增加之类的。

        但相对于刚讲过的动态规划：392.判断子序列就有难度了，这道题目双指针法可就做不了了，来看看动规五部曲分析如下：

1、确定dp数组以及下标的含义

        dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

2、确定递推公式

        这一类问题，基本是要分析两种情况。

s[i-1]与t[j-1]相等

s[i-1]与t[j-1]不相等

当s[i-1]与t[j-1]相等时，dp[i][j]可以有两部分组成。

        一部分是用s[i-1]来匹配，那么个数为dp[i-1][j-1]

        一部分是不用s[i-1]来匹配，那么个数为dp[i-1][j]

这里可能有些同学不明白了，为什么还要考虑 不用s[i-1]来匹配，都相同了指定要匹配啊。

举个例子：例如s = bagg, t = bag，那么s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即  用s[0]s[1]s[2]组成bag。

        所以当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[i-1]来匹配，即dp[i-1][j]

。所以递推公式dp[i][j] = dp[i-1][j]

3、dp数组如何初始化

        从递推公式dp[i][j] = dp[i-1][j-1]+dp[i-1][j] 和 dp[i][j] = dp[i-1][j] 中可以看出来dp[i][0]和dp[0][j]是一定要初始化的。

        每当初始化的时候，都要回顾一下dp[i][j]的定义，不要凭感觉初始化。

        dp[i][0]表示什么呢？

        dp[i][0]表示：以i-1结尾的s可以随便删除元素，出现空字符串的个数。

        那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。

        再来看dp[0][j]表示：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。

        那么dp[0][j]一定是0，因为s无论如何也变不成t啊。

        最后就要看一个特殊位置了，即dp[0][0] 应该是多少

dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。

初始化分析完毕，代码如下：

vector> dp(s.size() + 1, vector(t.size() + 1));
for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;
for (int j = 1; j <= t.size(); j++) dp[0][j] = 0; // 其实这行代码可以和dp数组初始化的时候放在一起，但我为了凸显初始化的逻辑，所以还是加上了。

4、确定遍历顺序

        从递推公式dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 和 dp[i][j] = dp[i-1][j]中可以看出来dp[i][j]都是根据左上方和正上方推出来的。

        所以遍历的时候一定是从上到下，从左到右，这样可以保证dp[i][j]可以根据之前计算出来的数值进行计算。代码如下

for (int i = 1; i <= s.size(); i++) {
    for (int j = 1; j <= t.size(); j++) {
        if (s[i - 1] == t[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        } else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}

5、举例推导dp数组

        以s："baegg"，t："bag"为例，推导dp数组状态如下：

 

        如果写出来的代码怎么改都通过不了，不妨把dp数组打印出来，看一看，是不是这样的。

动规五部曲分析完毕，代码如下：

func numDistinct(s string, t string) int {
    dp:= make([][]int,len(s)+1)
    for i:=0;i<len(dp);i++{
        dp[i] = make([]int,len(t)+1)
    }
    // 初始化
    for i:=0;i<len(dp);i++{
        dp[i][0] = 1
    }
    // dp[0][j] 为 0，默认值，因此不需要初始化
    for i:=1;i<len(dp);i++{
        for j:=1;j<len(dp[i]);j++{
            if s[i-1] == t[j-1]{
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            }else{
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[len(dp)-1][len(dp[0])-1]
}

再等等