2014
11-19

LeetCode-Distinct Subsequences[动态规划]

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.

// LeetCode, Distinct Subsequences
// 二维动规+滚动数组
// 时间复杂度O(m*n)，空间复杂度O(n)
class Solution {
public:
int numDistinct(const string &S, const string &T) {
vector<int> f(T.size() + 1);
f[0] = 1;
for (int i = 0; i < S.size(); ++i) {
for (int j = T.size() - 1; j >= 0; --j) {
f[j + 1] += S[i] == T[j] ? f[j] : 0;
}
}

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


Java代码:

public class Solution {
static int dp[][];
static int numDistinctRecr(char s[],char t[],int i,int j){
if(s.length - i < t.length - j) return 0;
if(j == t.length) return 1;
if( i >= s.length || j>= t.length ) return 0;
if(dp[i][j] >= 0) return dp[i][j];
if(s[i] == t[j]){ //当前这个字符相等
return (dp[i][j] = numDistinctRecr(s, t, i+1, j) + numDistinctRecr(s,t,i+1,j+1));
}else{//不同的只能删掉
return (dp[i][j] = numDistinctRecr(s, t, i+1,j ));
}
}

public static int numDistinct(String S, String T) {
dp = new int[S.length()][T.length()];
for(int i=0; i<S.length(); i++)
for(int j=0; j<T.length(); j++)
dp[i][j] = -1;
return numDistinctRecr(S.toCharArray(), T.toCharArray(), 0, 0);
}
}

1. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

3. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？