代码随想录Day_55打卡

①、判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

事例：

输入：s = "abc", t = "ahbgdc"
输出：true

思路：

        使用动态规划，其实就是跟之前一样寻找不连续的公共字符，若公共字符数量达到整个字符串s，就说明s是t的子序列。

动态规划：

        dp定义及含义：dp[i][j]表示s的前i - 1个字符与t的前j - 1个字符共有多少个匹配

        状态转移方程：if(s.charAt(i - 1) == t.charAt(t - 1)) dp[i][j] = dp[i - 1][j - 1] + 1 匹配得上

                                else dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1) 匹配不上

        初始化：都设为0

        遍历顺序：两层for循环嵌套遍历两个字符串，注意i,j对应的字符串即可

        dp[s.length()][t.length()]即为答案。

代码：

public boolean isSubsequence(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for(int i = 1;i <= s.length();i++){
            for(int j = 1;j <= t.length();j++){
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[s.length()][t.length()] == s.length();
    }

②、不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

事例：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

思路：

        与前面匹配的有点类似，只是这道题需要统计t完整出现的次数，使用动态规划的话，得改变下dp的含义。dp[i][j]表示在字符串s的前i个字符中共出现多少次字符串t(下标0到j - 1)。此时dp[0][0]表示空串包含多少个空串，初始化为1。故第一行为t是空串，都应初始化为1，其它初始化为0。

状态转移跟前面有些小变动，若匹配得上，则说明字符串s的第i - 1个字符有价值，能匹配上，若不匹配，则不能加上。故到s的第i个字符时，若匹配得上，则dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，若匹配不了，则dp[i][j] = dp[i - 1][j]。

动态规划：

        dp定义及含义：dp[i][j]表示在字符串s前i个字符中共有多少个字符串(t的前j个字符)。

        状态转移方程：if(s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] =  dp[i - 1][j - 1] + dp[i - 1][j]

                                else dp[i][j] = dp[i - 1][j]

        初始化：第一行初始化为1

        遍历顺序：两层for循环嵌套遍历

        dp[s.length()][t.length()]即为答案。

代码：

public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for(int i = 0;i <= s.length();i++){
            dp[i][0] = 1;
        }
        for(int i = 1;i <= s.length();i++){
            for(int j = 1;j <= t.length();j++){
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }

参考：代码随想录 (programmercarl.com)