快速建设网站外链,网站开发交接清单,北京seo网站设计,北京网页设计工资一般多少问题#xff1a; 给定一个字符串 s 和一个字符串 t #xff0c;计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指#xff0c;通过删除一些#xff08;也可以不删除#xff09;字符且不干扰剩余字符相对位置所组成的新字符串。#xff08;例如#xff0c; 给定一个字符串 s 和一个字符串 t 计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指通过删除一些也可以不删除字符且不干扰剩余字符相对位置所组成的新字符串。例如ACE 是 ABCDE 的一个子序列而 AEC 不是
题目数据保证答案符合 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
提示
0 s.length, t.length 1000 s 和 t 由英文字母组成 解答思路
1、题目分析
- 本题要求计算字符串 s 的子序列中字符串 t 出现的个数。
- 需要找到所有可能的匹配情况可以通过动态规划来解决。
2、主要思路
- 定义一个二维数组 dp其中 dp[i][j] 表示字符串 s 的前 i 个字符和字符串 t 的前 j 个字符的匹配情况。
- 初始化边界情况当 j0 时dp[i][0] 表示字符串 s 的前 i 个字符是否可以通过删除一些字符得到空字符串即 dp[i][0]1。
- 递推关系为如果 s[i]t[j]则 dp[i][j]dp[i-1][j-1]dp[i-1][j]否则 dp[i][j]dp[i-1][j]。
- 最终答案为 dp[s.length()][t.length()]。
以下是修改后的代码
java
class Solution { public int numDistinct(String s, String t) { int m s.length(), n t.length(); int[][] dp new int[m 1][n 1]; // 初始化边界情况 for (int i 0; i m; i) { dp[i][0] 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] dp[i - 1][j]; } else { dp[i][j] dp[i - 1][j]; } } } return dp[m][n]; }
} (文章为作者在学习java过程中的一些个人体会总结和借鉴如有不当、错误的地方请各位大佬批评指正定当努力改正如有侵权请联系作者删帖。)
