Lintcode: 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.

Tags Expand 

String Dynamic Programming

Reference:
https://yuanbin.gitbooks.io/algorithm/content/zh-cn/dynamic_programming/distinct_subsequences.html

1. Recursion
n -- len of S  m -- len of T
Time: O( A(m, n) )  worst case O(n!)
worst case stack Space: O(m * (n + m))    m -- stack level   m+n -- maximum space for each level

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

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 if(T.size() == 0) return 1; if(S.size() < T.size()) return 0; int num = 0; for(int i = 0; i < S.size(); i++){ if(S[i] == T[0]){ string s = S.substr(i + 1); string t = T.substr(1); num += numDistinct(s, t); } } return num; } };

2. DP
Time O(n*n)
Space: O(n*n)

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

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 vector< vector<int> > DP(S.size() + 1, vector<int>(T.size() + 1, 0 )); //DP[0][0] = 1; for(int i = 0; i <= S.size(); i++){ DP[i][0] = 1; } for(int i = 1; i <= S.size(); i++){ //DP[i][0] = 1; for(int j = 1; j <= T.size(); j++){ if(S[i - 1] == T[j - 1]) DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j]; else DP[i][j] = DP[i - 1][j]; } } return DP[S.size()][T.size()]; } };

3: DP-- space optimization
Key is the calculation from top to bottom, from left to right:
http://bangbingsyb.blogspot.com/2014/11/leetcode-distinct-subsequences.html