首页 > 代码库 > Distinct Subsequences
Distinct Subsequences
题目:
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE"
is a subsequence of "ABCDE"
while "AEC"
is not).
Here is an example:
S = "rabbbit"
, T = "rabbit"
Return 3
.
这个题目可以用动态规划来解,既然是动态规划,所以关键是要找到递推关系。
我们设S(i)表示第i个字符之前的S的子串(不包含第i个字符),同理设T(j)表示第j个字符之前的T的子串。
设C(i,j)表示S(i)中有T(j)的个数。
于是就有递推关系:
if (当第S(i)的最后一个字符与T(j)的最后一个字符不等时) C(i,j)=C(i-1,j)+C(i-1,i-1);
else C(i,j)=C(i-1,j)
在编写程序时自然可以利用一个二维数组table[i][j]来表示C(i,j)的值。
java code:
public class DistinctSubsequences { public static int numDistincts(String S, String T) { int[][] table = new int[S.length() + 1][T.length() + 1]; for (int i = 0; i <= S.length(); i++) { table[i][0] = 1;// 初始化S到T的空子串为1 } for (int i = 1; i <= S.length(); i++) { for (int j = 1; j <= T.length(); j++) { if (S.charAt(i - 1) == T.charAt(j - 1)) { table[i][j] = table[i - 1][j - 1] + table[i - 1][j]; } else { table[i][j] = table[i - 1][j]; } } } return table[S.length()][T.length()]; } public static void main(String[] args) { // String S = "b", T = "b"; // String S = "abc", T = ""; String S = "rabbbit", T = "rabbit"; System.out.println(numDistincts(S, T)); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。