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.
这道题是求字符串T是字符串S的字串的所有可能性的数目（不存在就是0）。
刚开始算的的时候比较暴力，所以超时了。
public class Solution {
char[] word1;
char[] word2;
int result = 0;
public int numDistinct(String s, String t) {
int len1 = s.length(),len2 = t.length();
if( len1 < len2 )
return 0;
word1 = s.toCharArray();
word2 = t.toCharArray();
for( int i = 0;i<=len1-len2;i++){
if( word1[i] == word2[0])
helper(i+1,1);
}
return result;
}
public void helper(int start1,int start2){
if( start2 == word2.length ){
result++;
return ;
}
for( int i = start1;i< word1.length ;i++){
if( word1[i] == word2[start2] )
helper(i+1,start2+1);
}
}
}
所以用DP算法。
DP，化归为二维地图的走法问题。
r a b b i t
1 0 0 0 0 0 0
r 1
a 1
b 1
b 1
b 1
i 1
t 1
如果当前字符相同，dp[i][j]结果等于用(dp[i-1][j-1])和(dp[i-1][j])求和
如果当前字符不同，dp[i][j] = dp[i-1][j]
public class Solution {
public int numDistinct(String s, String t) {
int len1 = s.length(),len2 = t.length();
if( len1 < len2 )
return 0;
char[] word1 = s.toCharArray();
char[] word2 = t.toCharArray();
int[][] dp = new int[len1+1][len2+1];
for( int i = 0;i<=len1;i++){
for( int j = 0;j<=i && j<=len2;j++){
if( i == 0 && j != 0)
dp[i][j] = 0;
else if( j == 0)
dp[i][j] = 1;
else if( word1[i-1] == word2[j-1] )
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[len1][len2];
}
}