## Wednesday, November 26, 2014

### [LeetCode] 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`.

1. 状态i, j分别表示T中长度为i的prefix：T[0:i-1]，和S中长度为j的prefix：S[0:j-1]。
DP[i][j]：S[0:j-1]中存在T[0:i-1]作为distinct subsequence的个数。显然如果j<i，DP[i][j] = 0。

2. 递推公式：
(a) T[i]!=s[j]:

T = r a b
S = r c a c b c

DP[i+1][j+1] = DP[i+1][j]

(b) T[i] = s[j]:

T = r a b b
S = r a b b b  - DP[i+1][j] = 1
S = r a b b b  - DP[i][j] = 2
S = r a b b  /

DP[i+1][j+1] = DP[i][j] + DP[i+1][j]

S[j-1]!= T[i-1]：DP[i][j] = DP[i][j-1]
S[j-1]==T[i-1]：DP[i][j] = DP[i-1][j-1] + DP[i][j-1]

3. 计算方向和起始状态：
DP[i][j]
DP[i+1][j]   DP[i+1][j+1]

T = r
S = r a r b r c

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

4. 计算优化：用滚动数组减少内存消耗。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20``` ```class Solution { public: int numDistinct(string S, string T) { int n = S.size(), m = T.size(); vector dp(n+1, 1); for(int i=1; i<=m; i++) { int upLeft = dp[0]; dp[0] = 0; for(int j=1; j<=n; j++) { int temp = dp[j]; dp[j] = dp[j-1]; if(S[j-1]==T[i-1]) dp[j] += upLeft; upLeft = temp; } } return dp[n]; } }; ```

1. My same way of space optimization:

public class Solution {
public int numDistinct(String s, String t) {
if(s == null || t == null || t.length() == 0) return 0;
int[] dp = new int[t.length()];

for(int i = 0; i=0; j–){
if(c == t.charAt(j)){
dp[j] = dp[j] + (j!=0?dp[j-1]: 1);
}
}
}
return dp[t.length()-1];
}
}
URL: http://traceformula.blogspot.com/2015/08/distinct-subsequences.html

2. My same way of space optimization:

public class Solution {
public int numDistinct(String s, String t) {
if(s == null || t == null || t.length() == 0) return 0;
int[] dp = new int[t.length()];

for(int i = 0; i=0; j–){
if(c == t.charAt(j)){
dp[j] = dp[j] + (j!=0?dp[j-1]: 1);
}
}
}
return dp[t.length()-1];
}
}
URL: http://traceformula.blogspot.com/2015/08/distinct-subsequences.html