LintCode (118) 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).

Have you met this question in a real interview? 

Yes

Example

Given S = "rabbbit", T = "rabbit", return 3.

Challenge

Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

挺别扭的一道题，知道是DP无从下口，看了提示写的

f[i][j]为从A的前i中取B中的前j个字符的方案数，

那么当a[i]==b[j]的时候为f[i-1][j]+f[i-1][j-1], 否则为f[i-1][j-1]， 仔细想想是那么回事，不过是没想出来。。。

初始化的时候初始化[0][*]和[*][0]，

最后为f[m][n]

空间为o(m,n), 复杂度o(mn)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: /** * @param S, T: Two string. * @return: Count the number of distinct subsequences */ int numDistinct(string &S, string &T) { // write your code here int m=S.size(); int n=T.size(); vector< vector<int> > f(m+1, vector<int>(n+1, 0)); for (int i=0; i<=m; i++){ f[i][0]=1; } for (int i=1; i<=n; i++){ f[0][i]=0; } for (int i=1; i<=m; i++){ for (int j=1; j<=n; j++){ f[i][j]=f[i-1][j]; if (S[i-1]==T[j-1]) f[i][j]+=f[i-1][j-1]; } } return f[m][n]; } };

为了减小空间复杂度，用下滚动数组

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: /** * @param S, T: Two string. * @return: Count the number of distinct subsequences */ int numDistinct(string &S, string &T) { // write your code here int m=S.size(); int n=T.size(); vector< vector<int> > f(2, vector<int>(n+1, 0)); f[0][0]=f[1][0]=1; for (int i=1; i<=n; i++){ f[0][i]=0; } for (int i=1; i<=m; i++){ for (int j=1; j<=n; j++){ f[i%2][j]=f[(i-1)%2][j]; if (S[i-1]==T[j-1]) f[i%2][j]+=f[(i-1)%2][j-1]; } } return f[m%2][n]; } };