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.

C++:
01 class Solution {
02 public:
03     int numDistinct(string S, string T) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int n=S.size();
07         int m=T.size();
08         if(n<m)
09             return 0;
10         vector<int*> A(m+1);
11         for(int i=0;i<=m;i++)
12         {
13             A[i]=new int[n+1];
14             for(int j=0;j<=n;j++)
15             {
16                 A[i][j]=0;
17             }
18         }
19         for(int i=0;i<=n;i++)
20         {
21             A[m][i]=1;
22         }
23         for(int i=1;i<=m;i++)
24         {
25             for(int j=0;j<=ni;j++)
26             {
27                 A[mi][nij]=A[mi][nij+1];
28                 if(T[mi]==S[nij])
29                 {
30                     A[mi][nij]+=A[mi+1][nij+1];
31                 }
32             }
33             for(int j=1;j<=mi;j++)
34             {
35                 A[mij][ni]=A[mij][ni+1];
36                 if(T[mij]==S[ni])
37                 {
38                     A[mij][ni]+=A[mij+1][ni+1];
39                 }
40             }
41         }
42         return A[0][0];
43     }
44 };
Advertisements
This entry was posted in Array and linked list, Dynamic programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s