现在的位置: 首页 > 综合 > 正文

[LeetCode] Distinct Subsequences

2017年12月23日 ⁄ 综合 ⁄ 共 827字 ⁄ 字号 评论关闭

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.

简单DP,一次写过,还不错~ 就是写的时候发现滚动数组写得还是不太熟。

class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    	int ns=S.length(),nt=T.length();
		if (ns < nt )
			return 0;
		vector<vector<int> > dp(2,vector<int>(nt+1,0));
		dp[0][0]=1;
		for(int i=1;i<=ns;i++)
		{
			vector<int>& cur =dp[i%2];
			vector<int>& pre =dp[(i-1)%2];
			cur[0]=1;
			for(int j=1;j<=nt;j++)
			{
				if ( i < j )
					break;
				if ( S[i-1]==T[j-1] )
					cur[j]=pre[j-1]+pre[j];
				else
					cur[j]=pre[j];
			}
		}
		return dp[ns%2][nt];
    }
};

抱歉!评论已关闭.