# Distinct Subsequences

## Question

### Problem Statement

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

### Python

class Solution:
# @param S, T: Two string.
# @return: Count the number of distinct subsequences
def numDistinct(self, S, T):
if S is None or T is None:
return 0
if len(S) < len(T):
return 0
if len(T) == 0:
return 1

num = 0
for i, Si in enumerate(S):
if Si == T[0]:
num += self.numDistinct(S[i + 1:], T[1:])

return num


### C++

class Solution {
public:
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
int numDistinct(string &S, string &T) {
if (S.size() < T.size()) return 0;
if (T.empty()) return 1;

int num = 0;
for (int i = 0; i < S.size(); ++i) {
if (S[i] == T[0]) {
string Si = S.substr(i + 1);
string t = T.substr(1);
num += numDistinct(Si, t);
}
}

return num;
}
};


### Java

public class Solution {
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String S, String T) {
if (S == null || T == null) return 0;
if (S.length() < T.length()) return 0;
if (T.length() == 0) return 1;

int num = 0;
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == T.charAt(0)) {
// T.length() >= 1, T.substring(1) will not throw index error
num += numDistinct(S.substring(i + 1), T.substring(1));
}
}

return num;
}
}


### 源码分析

1. 对 null 异常处理(C++ 中对 string 赋NULL 是错的，函数内部无法 handle 这种情况)
2. S 字符串长度若小于 T 字符串长度，T 必然不是 S 的子序列，返回0
3. T 字符串长度为0，证明 T 是 S 的子序列，返回1

## 题解2 - Dynamic Programming

1. S[i] == T[j]: 两个字符串的最后一个字符相等，我们可以选择 S[i] 和 T[j] 配对，那么此时有 f[i][j] = f[i-1][j-1]; 若不使 S[i] 和 T[j] 配对，而是选择 S[0:i-1] 中的某个字符和 T[j] 配对，那么 f[i][j] = f[i-1][j]. 综合以上两种选择，可得知在S[i] == T[j]时有 f[i][j] = f[i-1][j-1] + f[i-1][j]
2. S[i] != T[j]: 最后一个字符不等时，S[i] 不可能和 T[j] 配对，故 f[i][j] = f[i-1][j]

### Python

class Solution:
# @param S, T: Two string.
# @return: Count the number of distinct subsequences
def numDistinct(self, S, T):
if S is None or T is None:
return 0
if len(S) < len(T):
return 0
if len(T) == 0:
return 1

f = [[0 for i in xrange(len(T) + 1)] for j in xrange(len(S) + 1)]
for i, Si in enumerate(S):
f[i][0] = 1
for j, Tj in enumerate(T):
if Si == Tj:
f[i + 1][j + 1] = f[i][j + 1] + f[i][j]
else:
f[i + 1][j + 1] = f[i][j + 1]

return f[len(S)][len(T)]


### C++

class Solution {
public:
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
int numDistinct(string &S, string &T) {
if (S.size() < T.size()) return 0;
if (T.empty()) return 1;

vector<vector<int> > f(S.size() + 1, vector<int>(T.size() + 1, 0));
for (int i = 0; i < S.size(); ++i) {
f[i][0] = 1;
for (int j = 0; j < T.size(); ++j) {
if (S[i] == T[j]) {
f[i + 1][j + 1] = f[i][j + 1] + f[i][j];
} else {
f[i + 1][j + 1] = f[i][j + 1];
}
}
}

return f[S.size()][T.size()];
}
};


### Java

public class Solution {
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String S, String T) {
if (S == null || T == null) return 0;
if (S.length() < T.length()) return 0;
if (T.length() == 0) return 1;

int[][] f = new int[S.length() + 1][T.length() + 1];
for (int i = 0; i < S.length(); i++) {
f[i][0] = 1;
for (int j = 0; j < T.length(); j++) {
if (S.charAt(i) == T.charAt(j)) {
f[i + 1][j + 1] = f[i][j + 1] + f[i][j];
} else {
f[i + 1][j + 1] = f[i][j + 1];
}
}
}

return f[S.length()][T.length()];
}
}


### 复杂度分析

#### Java

public class Solution {
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String S, String T) {
if (S == null || T == null) return 0;
if (S.length() < T.length()) return 0;
if (T.length() == 0) return 1;

int[] f = new int[T.length() + 1];
f[0] = 1;
for (int i = 0; i < S.length(); i++) {
for (int j = T.length() - 1; j >= 0; j--) {
if (S.charAt(i) == T.charAt(j)) {
f[j + 1] += f[j];
}
}
}

return f[T.length()];
}
}


powered by