@TOC


前言

代码随想录算法训练营day55


一、Leetcode 392.判断子序列

1.题目

给定字符串 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
两个字符串都只由小写字符组成。

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/is-subsequence

2.解题思路

方法一:双指针

思路及算法

本题询问的是,ss 是否是 tt 的子序列,因此只要能找到任意一种 ss 在 tt 中出现的方式,即可认为 ss 是 tt 的子序列。

而当我们从前往后匹配,可以发现每次贪心地匹配靠前的字符是最优决策。

假定当前需要匹配字符 cc,而字符 cc 在 tt 中的位置 x1x1​ 和 x2x2​ 出现(x1<x2x1​<x2​),那么贪心取 x1x1​ 是最优解,因为 x2x2​ 后面能取到的字符,x1x1​ 也都能取到,并且通过 x1x1​ 与 x2x2​ 之间的可选字符,更有希望能匹配成功。

这样,我们初始化两个指针 ii 和 jj,分别指向 ss 和 tt 的初始位置。每次贪心地匹配,匹配成功则 ii 和 jj 同时右移,匹配 ss 的下一个位置,匹配失败则 jj 右移,ii 不变,尝试用 tt 的下一个字符匹配 ss。

最终如果 ii 移动到 ss 的末尾,就说明 ss 是 tt 的子序列。

3.代码实现

```java class Solution { public boolean isSubsequence(String s, String t) { int n = s.length(), m = t.length(); int i = 0, j = 0; while (i < n && j < m) { if (s.charAt(i) == t.charAt(j)) { i++; } j++; } return i == n; } }

```

二、Leetcode 115.不同的子序列

1.题目

给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数。

题目数据保证答案符合 32 位带符号整数范围。

示例 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 由英文字母组成

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/distinct-subsequences

2.解题思路

方法一:动态规划

假设字符串 ss 和 tt 的长度分别为 mm 和 nn。如果 tt 是 ss 的子序列,则 ss 的长度一定大于或等于 tt 的长度,即只有当 m≥nm≥n 时,tt 才可能是 ss 的子序列。如果 m

当 m≥nm≥n 时,可以通过动态规划的方法计算在 ss 的子序列中 tt 出现的个数。

创建二维数组 dpdp,其中 dp[i][j]dp[i][j] 表示在 s[i:]s[i:] 的子序列中 t[j:]t[j:] 出现的个数。

上述表示中,s[i:]s[i:] 表示 ss 从下标 ii 到末尾的子字符串,t[j:]t[j:] 表示 tt 从下标 jj 到末尾的子字符串。

考虑动态规划的边界情况:

当 j=nj=n 时,t[j:]t[j:] 为空字符串,由于空字符串是任何字符串的子序列,因此对任意 0≤i≤m0≤i≤m,有 dp[i][n]=1dp[i][n]=1;

当 i=mi=m 且 j<nj<n 时,s[i:]s[i:] 为空字符串,t[j:]t[j:] 为非空字符串,由于非空字符串不是空字符串的子序列,因此对任意 0≤j<n0≤j<n,有 dp[m][j]=0dp[m][j]=0。

当 i

当 s[i]=t[j]s[i]=t[j] 时,dp[i][j]dp[i][j] 由两部分组成:

    如果 s[i]s[i] 和 t[j]t[j] 匹配,则考虑 t[j+1:]t[j+1:] 作为 s[i+1:]s[i+1:] 的子序列,子序列数为 dp[i+1][j+1]dp[i+1][j+1];

    如果 s[i]s[i] 不和 t[j]t[j] 匹配,则考虑 t[j:]t[j:] 作为 s[i+1:]s[i+1:] 的子序列,子序列数为 dp[i+1][j]dp[i+1][j]。

因此当 s[i]=t[j]s[i]=t[j] 时,有 dp[i][j]=dp[i+1][j+1]+dp[i+1][j]dp[i][j]=dp[i+1][j+1]+dp[i+1][j]。

当 s[i]≠t[j]s[i]​=t[j] 时,s[i]s[i] 不能和 t[j]t[j] 匹配,因此只考虑 t[j:]t[j:] 作为 s[i+1:]s[i+1:] 的子序列,子序列数为 dp[i+1][j]dp[i+1][j]。

因此当 s[i]≠t[j]s[i]​=t[j] 时,有 dp[i][j]=dp[i+1][j]dp[i][j]=dp[i+1][j]。

由此可以得到如下状态转移方程:

dp[i][j]={dp[i+1][j+1]+dp[i+1][j],s[i]=t[j]dp[i+1][j],s[i]≠t[j]dp[i][j]={dp[i+1][j+1]+dp[i+1][j],dp[i+1][j],​s[i]=t[j]s[i]​=t[j]​

最终计算得到 dp[0][0]dp[0][0] 即为在 ss 的子序列中 tt 出现的个数。

3.代码实现

```java class Solution { public int numDistinct(String s, String t) { int m = s.length(), n = t.length(); if (m < n) { return 0; } int[][] dp = new int[m + 1][n + 1]; for (int i = 0; i <= m; i++) { dp[i][n] = 1; } for (int i = m - 1; i >= 0; i--) { char sChar = s.charAt(i); for (int j = n - 1; j >= 0; j--) { char tChar = t.charAt(j); if (sChar == tChar) { dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]; } else { dp[i][j] = dp[i + 1][j]; } } } return dp[0][0]; } }

```

08-18 17:46