LeetCode Distinct Subsequences

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.


这问题描述不清,题目想问S中有多少个不同的subsequence等于T,这里的不同是指形成subsequence的方法不同,比如样例中,rabbbit可以去掉中间任意一个b都能形成T,所以不同的方法有3种。

这是典型的动态规划问题。假设dp[i][j]表示由S[1,...,i]变到T[1,...,j]有多少种subsequence方法。此时我们有两种选择,如果S[i]!=T[j],则等价于由S[1,...,i-1]变到T[1,...,j],所以dp[i][j]=dp[i-1][j];如果S[i]==T[j],则还可以由S[1,...,i-1]变到T[1,...,j-1],所以dp[i][j]+=dp[i-1][j-1]。

DP转移公式如下:

dp[i][j]=\begin{cases}dp[i-1][j] & \text{if $S[i]\neq T[j]$}\\dp[i-1][j]+dp[i-1][j-1] & \text{if $S[i]=T[j]$}\\\end{cases}

为了便于理解,我们先在s和t的开头添加一个哨兵字符'^',初始值dp[i][0]=1,因为由任意字符串转换为空字符串只有一种方法,就是把s中的字符全删了;dp[0][j]=0,因为空字符串的subsequence不可能是是某个非空字符串。

完整代码如下:

class Solution {
public:
	int numDistinct(string s, string t) {
		if (s == "")
			return 0;
		if (t == "")
			return 1;
		s = "^" + s;
		t = "^" + t;
		int n = s.size(), m = t.size();
		vector<vector<int>> dp(n, vector<int>(m, 0));
		for (int i = 0; i < n; i++)
			dp[i][0] = 1; // '*' -> '' 1 sub
		for (int i = 1; i < n; i++)
		{
			for (int j = 1; j < m; j++)
			{
				dp[i][j] = dp[i - 1][j];
				if (s[i] == t[j])
					dp[i][j] += dp[i - 1][j - 1];
			}
		}
		return dp[n - 1][m - 1];
	}
};

本代码提交AC,用时20MS。

Leave a Reply

Your email address will not be published. Required fields are marked *