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.

Solution: using dynamic programming. Initiating a two dimensional array of m*n, where n and m are the lengths of S and T respectively. An array entry array[i][j] indicate the number of subsequences of the first i characters in T, within the first j characters in S. 

First, initiating the first line. The if S.charAt(0) and T.charAt(0) is the same, the first entry of array should be 1. Then we look if the first character of T appear again in S. If so, we increment the value of the entry by one.

2. The first column except array[0][0] should all be 0.

3. Then, updating the inside elements.

     if the ith character of T is the same as the jth character of S, a new match occurs. array[i][j] is calculated by summing up the entry in its left up cell (indicating the condition before handling the current characters in both array) and the entry in its left cell (indicating the matching before introducing the current character in array S).

If they are not the same, just copy the number from its left cell, indicating there is no new match.

4. In the end, simply return array[n-1][m-1].

     r  a  b  b  b  i  t

r   1  1  1  1  1  1  1
a   0  1  1  1  1  1  1
b   0  0  1  2  3  3  3

b   0  0  0  1  3  3  3

i    0  0  0  0  0  3  3
t    0  0  0  0  0  0  3

Java语言: DistinctSubsequences

01 public int numDistinct(String S, String T) {
02     int m=S.length();
03     int n=T.length();
04   
05     if(m==0 || n==0)
06         return 0;
07     // use dp, set up a two dimensional array to keep the temporal result
08     int[][] array=new int[n][m];
09     //initiate the result of comparing first characters
10     if(S.charAt(0)==T.charAt(0))
11     {
12         array[0][0]=1;
13     }
14     //initiate the first line
15     for(int j=1;j< m; j++)
16     {
17         if(S.charAt(j)==T.charAt(0))
18         {
19             array[0][j]=array[0][j-1]+1;
20         }
21         else
22         {
23             array[0][j]=array[0][j-1];
24         }
25     }      
26     //keep going through each character
27     //if two characters are same, result is the current number
28     //+ previous number of matched sequence before this character
29     // otherwise, keep the current number
30     for(int i=1;i<n;i++)
31     {
32         for(int j=1;j<m;j++)
33         {
34             if(T.charAt(i)==S.charAt(j))
35             {
36                 array[i][j]=array[i-1][j-1]+array[i][j-1];
37             }
38             else
39             {
40                 array[i][j]=array[i][j-1];
41             }
42         }
43     }
44   
45     return array[n-1][m-1];
46 }