17.zwd一起做网站池尾站,成都手机wap网站制作,jfinal网站开发模板,青州市网站建设一、题目描述
给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数#xff0c;结果需要对 10^9 7 取模。 示例 1#xff1a;
输入#xff1a;s rabbbit, t rabbit
输出#xff1a;3
解释#xff1a;
如下所示, 有 …一、题目描述
给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 10^9 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 1000s 和 t 由英文字母组成
二、解题思路
这个问题可以通过动态规划来解决。我们可以创建一个二维数组 dp其中 dp[i][j] 表示在 s 的前 i 个字符中包含 t 的前 j 个字符的子序列的数量。我们需要填充这个数组来找到最终的答案。
对于动态规划数组 dp 的填充我们有以下几种情况
1. 如果 s 的第 i 个字符等于 t 的第 j 个字符那么 dp[i][j] 可以由两部分组成
不使用 s 的第 i 个字符只考虑前 i-1 个字符和 t 的前 j 个字符的匹配情况即 dp[i-1][j]。使用 s 的第 i 个字符考虑 s 的前 i-1 个字符和 t 的前 j-1 个字符的匹配情况即 dp[i-1][j-1]。
2. 如果 s 的第 i 个字符不等于 t 的第 j 个字符那么我们只能忽略 s 的第 i 个字符dp[i][j] 应该等于 dp[i-1][j]。
初始化时dp[0][0] 应该为 1因为两个空字符串的匹配情况只有一种即不使用任何字符。其他的 dp[i][0] 应该为 1因为 t 为空字符串时匹配情况只有一种即忽略所有 s 的字符。
三、具体代码
class Solution {public int numDistinct(String s, String t) {int MOD 1000000007;int m s.length();int 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] dp[i - 1][j - 1]) % MOD;} else {dp[i][j] dp[i - 1][j];}}}return dp[m][n];}
}四、时间复杂度和空间复杂度
1. 时间复杂度
我们定义了两个循环一个遍历字符串 s 的每个字符另一个遍历字符串 t 的每个字符。外层循环遍历 s 的长度 m内层循环遍历 t 的长度 n。在循环的每一次迭代中我们执行了常数时间的操作包括字符比较和模运算。因此时间复杂度是 O(m * n)其中 m 是字符串 s 的长度n 是字符串 t 的长度。
2. 空间复杂度
我们定义了一个二维数组 dp其大小为 (m 1) x (n 1)其中 m 和 n 分别是字符串 s 和 t 的长度。这个数组用于存储每个子问题的解即 s 的前 i 个字符中包含 t 的前 j 个字符的子序列的数量。因此空间复杂度是 O(m * n)这是因为我们需要存储所有子问题的解。
五、总结知识点 动态规划这是一种通过将问题分解为更小的子问题来解决复杂问题的方法通常用于优化问题。在本题中我们使用动态规划来计算字符串 s 中包含字符串 t 的子序列的数量。 二维数组代码中使用了一个二维数组 dp 来存储动态规划的状态。二维数组是一种常用的数据结构用于存储具有两个维度的数据。 字符串操作代码中使用了 charAt 方法来获取字符串中特定位置的字符这是字符串操作的基本技巧。 模运算由于结果需要对一个大数 10^9 7 取模代码中使用了模运算来避免整数溢出并保持结果在一个合理的范围内。 边界条件处理在动态规划的初始化阶段我们将 dp[i][0] 设置为 1这是因为一个空字符串总是另一个字符串的子序列且只有一种方式可以实现。 循环结构代码中使用了两个嵌套的循环来遍历字符串 s 和 t 的所有字符这是实现动态规划的典型结构。 递推关系代码中建立了动态规划的递推关系即如果当前字符匹配则新的状态值是上方和左上方的值之和如果不匹配则新的状态值等于上方的值。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
