给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
示例 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
^^^
思路
- 求一个字符串S有多少种删除字符的方法可以得到字符串T
- 动态规划
dp[i][j]代表T前i个字符可以有S前j个字符组成的最大的个数- 递推方程
d[i][j] = dp[i -1][j - 1] + dp[i][j - 1],s[j] = s[i]dp[i][j] = dp[i][j - 1],s[j] != T[i]
`
代码
- 二维动态数组
public class Solution{
public int numDistinct(String s,String t) {
int[][] dp = new int[t.length() + 1][s.length() + 1];
for (int i = 0;i <= s.length();i++) {
dp[0][i] = 1;
}
for (int i = 1;i < t.length() + 1;i++) {
for (int j = 1;j < s.length() + 1;j++) {
if (t.charAt(i - 1) != s.charAt(j - 1)) {
dp[i][j] = dp[i][j - 1];
} else {
dp[i][j] = dp[i -1][j -1] + dp[i][j - 1];
}
}
}
return dp[t.length()][s.length()];
}
}
- 一维动态数组
public class Solution{
public int numDistinct(String s,String t) {
int[] dp = new int[s.length() + 1];
for (int i = 0;i <= s.length();i++) {
dp[i] = 1;
}
for (int i = 1;i < t.length() + 1;i++) {
int pre = dp[0];
dp[0] = 0;
for (int j = 1;j < s.length() + 1;j++) {
int tmp = dp[j];
if (t.charAt(i-1) != s.charAt(j-1)) {
dp[j] = dp[j - 1];
} else {
dp[j] = dp[j - 1] + pre;
}
pre = tmp;
}
}
return dp[s.length()];
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
