北京网站开发网站建设价格,莆田网站 建设,wordpress安装图片,制作wordpress模板教程视频教程题目链接
leetcode在线oj题——不同的子序列
题目描述
给定一个字符串 s 和一个字符串 t #xff0c;计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指#xff0c;通过删除一些#xff08;也可以不删除#xff09;字符且不干扰剩余字符相对位置所组成的新…题目链接
leetcode在线oj题——不同的子序列
题目描述
给定一个字符串 s 和一个字符串 t 计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指通过删除一些也可以不删除字符且不干扰剩余字符相对位置所组成的新字符串。例如“ACE” 是 “ABCDE” 的一个子序列而 “AEC” 不是
题目数据保证答案符合 32 位带符号整数范围。
题目示例
输入s “rabbbit”, t “rabbit” 输出3 解释 如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。 rabbbit rabbbit rabbbit
输入s “babgbag”, t “bag” 输出5 解释 如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。 babgbag babgbag babgbag babgbag babgbag
题目提示
0 s.length, t.length 1000s 和 t 由英文字母组成
解题思路
我们将问题分解为s的前i个字符的子序列中 t的前j个字符 出现的个数 先创建一个二维数组行代表t的每一个字符列代表s的每一个元素 其中arr[i][j]就代表s的前i个字符的子序列中 t的前j个字符 出现的个数 例如arr[4][3]就是rabb的子序列中rab出现的次数
arr[3][0]代表rab的子序列中空字符串出现的次数显然将所有的字符都删除后就是空字符串因此是1
而arr[0][3]代表空字符串的子序列中rab出现的次数显然是0
arr[0][0]代表空字符串的子序列中空字符串出现的次数显然是1
那么起始状态如下
那么我们来考虑一下arr[i][j]等于多少
如果s中的第i个字符和t中的第j个字符不相等
那么显然s需要删除最后一个字符才能够有可能和t相等因此 arr[i][j] arr[i - 1][j]
例如s是racbt是rac必须要删除s的最后一个字符b才有可能和t相等
如果s中的第i个字符和t中的第j个字符相等
可以分为下面两种情况
不删除s中的第i个字符删除s中的第i个字符
如果不删除s中的第i个字符我们就不用考虑t的最后一个字符了只需要考虑s的前i - 1个字符的子序列中t的前j - 1个字符出现的次数 因此 arr[i][j] arr[i - 1][j - 1] 例如racb和rab我们可以直接考虑rac的子序列中ra出现的次数
如果删除s中的第i个字符那么就相当于s的前i - 1个字符的子序列中t的前j个字符出现的次数 arr[i][j] arr[i - 1][j]
例如rabb和rab当我们删除rabb的第二个b后就相当于rab的子序列中rab出现的次数
因此将这两种情况合并可以得到 arr[i][j] arr[i - 1][j - 1] arr[i - 1][j]
最后返回arr[row][col]即可
代码
class Solution {public int numDistinct(String s, String t) {int row s.length();int col t.length();int[][] arr new int[row 1][col 1];arr[0][0] 1;for (int i 1; i row; i) {arr[i][0] 1;for (int j 1; j col; j) {if(s.charAt(i - 1) t.charAt(j - 1)){arr[i][j] arr[i - 1][j - 1] arr[i - 1][j];} else {arr[i][j] arr[i - 1][j];}}}return arr[row][col];}
}
