代码随想录算法训练营第55天| 392.判断子序列 115.不同的子序列

JAVA代码编写

392.判断子序列

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

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

进阶：

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

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

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

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

教程：https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html

方法一：动态规划

思路：

五部曲

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

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.数组初始化

初始化均为0

4.遍历顺序

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

5.举个例子

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

复杂度分析：

• 时间复杂度：O(mn)，其中m和n分别表示字符串s和字符串t的长度。
• 空间复杂度：O(mn)

class Solution {
    public boolean isSubsequence(String s, String t) {
        int m = s.length(); 
        int n = t.length();
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[m][n] == m ? true: false;
    }
}

方法二：双指针法

思路：初始化两个指针i和j，分别指向s和t的起始位置。

然后，进入循环，循环条件是i小于s的长度且j小于t的长度。在每次循环中，比较s.charAt(i)和t.charAt(j)两个字符是否相等，如果相等，则说明s中的当前字符匹配到了t中的当前字符，此时将i向后移动一位，表示已经匹配成功一个字符。

无论是否匹配成功，都将j向后移动一位，继续比较下一个字符。

最后，循环结束后，判断i是否等于s的长度，如果相等，则说明s中的所有字符都成功匹配到了t的子序列中，返回true，否则返回false。

复杂度分析：

• 时间复杂度：O(min(s.length(), t.length()))，其中s.length()和t.length()分别表示字符串s和字符串t的长度。
• 空间复杂度：O(1)

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == s.length();
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isSubsequence("abc","ahbgdc"));
    }
}

115.不同的子序列

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

教程：https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html

方法一：动态规划

思路：

五部曲

1.定义数组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子串和t子串的最后一位字母，所以只需要 dp[i-1] [j-1]。

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

所以当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]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1] [j]

所以递推公式为：dp[i] [j] = dp[i - 1] [j];

3.数组初始化

 for (int i = 0; i < s.length() + 1; i++) {
     dp[i][0] = 1;
 }

4.遍历顺序

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

5.举个例子

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

复杂度分析：

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < s.length() + 1; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < t.length() + 1; 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()];
    }
}