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.

Analysis:

We definte the state d[i][j] as the number of distinct subseq of T[0...j-1] in S[0...i-1]. For d[i][j], we have two operations: 1. Retain the char S[i-1], 2. Delete the char S[i-1]. For each d[i][j], we have two different situations:

1. S[i-1]!=T[j-1]: The only operation we can do is deleting the char S[i-1], otherwise, we cannot get a sequence T[0..j-1] in S[0...i-1]. Then d[i][j] equals to the number of dseq of T[0...j-1] in S[0...i-2], because for each of such cases, we delete the S[i-1] and we will get one case for d[i][j].

2. S[i-1]==T[j-1]: We can do either of the two operations. For deleting operation, d[i][j] = d[i-1][j]. For retainning operation, we then consider the cases for d[i-1][j-1]. For each of such cases, we retain the char S[i-1] and we will get one case in d[i][j]. As a result, d[i][j]=d[i-1][j]+d[i-1][j-1].

To summrize, after defining the state, we should start from what kind of operations we can do at current state, and identify different situations and the operations can be done in each situtaion.

Solution:

 1 public class Solution { 2     public int numDistinct(String S, String T) { 3         int len1 = S.length(); 4         int len2 = T.length(); 5  6         int[][] d = new int[len1+1][len2+1]; 7         for (int i=0;i<=len1;i++) Arrays.fill(d[i],0); 8         for (int i=0;i<=len1;i++) d[i][0] = 1; 9 10         for (int i=1;i<=len1;i++){11             int end = i;12             if (end>len2) end = len2;13             for (int j=1;j<=end;j++)14                 if (S.charAt(i-1)!=T.charAt(j-1))15                     d[i][j] = d[i-1][j];16                 else d[i][j] = d[i-1][j]+d[i-1][j-1];17         }18 19         return d[len1][len2];        20     }21 }

Leetcode-Distinct Subsequences