[LeetCode]Distinct Subsequences

对于string S和T，我们要找S中有多少不同的和T一样的subsequence。用DP[i][j]表示T的前i个char和S的前j个char有多少个distinct subsequence，我们可以得到递推方程：

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

第二个公式比较好理解，如何理解第一个递推公式呢？第一项DP[i][j - 1]代表不考虑S[j]原有的distinct subsequence，第二项DP[i - 1][j - 1]代表我们将T[i]和S[j]match之后，新加上的distinct subsequence。假设T长m，S长m，时间复杂度O(m * n)，空间复杂度O(m * n)，代码如下：

	class Solution {
	public:
	int numDistinct(string s, string t) {
	int lenT = t.size(), lenS = s.size();
	if(lenT > lenS)return 0;
	//dp[i][j] represents distinct subsequences for first i chars in T and first j chars in S
	vector<vector<int>> dp(lenT + 1, vector<int>(lenS + 1, 0));
	for(int i = 0; i <= lenT; ++i)
	{
	for(int j = i; j <= lenS; ++j)
	{
	//filling first row with ones
	if(!i)
	{
	dp[i][j] = 1;
	continue;
	}
	if(t[i - 1] == s[j - 1])
	dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
	else
	dp[i][j] = dp[i][j - 1];
	}
	}
	return dp[lenT][lenS];
	}
	};

view raw Distinct Subsequences_1.cpp hosted with ❤ by GitHub

空间可以优化为O(m)，代码如下：

	class Solution {
	public:
	int numDistinct(string s, string t) {
	int lenT = t.size(), lenS = s.size();
	if(lenT > lenS)return 0;
	//dp[i][j] represents distinct subsequences for first i chars in T and first j chars in S
	vector<int> dp(lenS + 1, 1);
	for(int i = 1; i <= lenT; ++i)
	{
	int cache = dp[i - 1];
	dp[i - 1] = 0;
	for(int j = i; j <= lenS; ++j)
	{
	int temp = dp[j];
	if(t[i - 1] == s[j - 1])
	dp[j] = dp[j - 1] + cache;
	else
	dp[j] = dp[j - 1];
	cache = temp;
	}
	}
	return dp[lenS];
	}
	};

view raw Distinct Subsequences_2.cpp hosted with ❤ by GitHub