# Different Subsequence

``````给出S = "rabbbit", T = "rabbit"

``````

## Solution

1. T的最后一个字符和S[k]匹配，
2. T的最后一个字符不和S[k]匹配。a相当于子问题:从S[0...lens-2]中删除几个字符得到T[0...lent-2]，b相当于子问题：从S[0...lens-2]中删除几个字符得到T[0...lent-1]。那么总的删除方法等于a、b两种情况的删除方法的和。递归解法代码如下，但是通过大数据会超时：

• 如果`S[i] = T[j], dp[i][j] = dp[i-1][j-1]+dp[i-1][j]`
• 如果`S[i]` 不等于 `T[j]`, `dp[i][j] = dp[i-1][j]`

Consider s=”EEACC” and t=”EAC”. num[i][j] means how many distinct sequence for T[0..i-1] in S[0..j-1]

Two cases for each num[i][j]:

num[i][j] inherits from num[i][j-1]. This means overlooking s[j], t[0..i] at least keeps the number of distinct sequences in s[0..j-1]. This case finds all sequences of t[0..i] in s[o..j] without s[j].

if t[i]==s[j], this means t[i] could be mapped to s[j], we cannot overlook s[j]. We look at the number of t[0..i-1] in s[0..j-1], and add it to the result. This case finds all sequences of t[0..i] in s[o..j] with s[j].

## Code

``````public class Solution {
public int numDistinct(String S, String T) {
int M = S.length();
int N = T.length();
int[] dp = new int[N+1];
Arrays.fill(dp, 0);
dp[0] = 1;
for (int i = 1; i <= M; ++i) {
for (int j = N; j >=1; --j) {
dp[j] = dp[j] + (S.charAt(i-1) == T.charAt(j-1) ? dp[j-1] : 0);
}
}
return dp[N];
}
}
``````

``````public class Solution {
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String s, String t) {
if (s==null || t==null || (s.length()==0 && t.length()!=0)) return 0;
if (t.length()==0) return 1;
int[] pre = new int[s.length()+1];
Arrays.fill(pre,1);
for (int i=1; i<=t.length(); i++){
int[] cur = new int[s.length()+1];
cur[0] = 0;
for (int j=1; j<=s.length(); j++){
if (s.charAt(j-1)==t.charAt(i-1)){
cur[j]+=pre[j-1];
}
cur[j] += cur[j-1];
}
System.arraycopy(cur, 0, pre, 0, cur.length);
}
return pre[s.length()];
}
}

``````