I***C
发帖数: 765 | 1 我用递归做的，小的test case都过了，大的test case运行时间过长。返不回答案，
哪位做过分享一下经验吧，谢谢
---------------------
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.
---------------------
method interface：
int numDistinct(string S, string T)
--------------------
Test cases
"
aabdbaabeeadcbbdedacbbeecbabebaeeecaeabaedadcbdbcdaabebdadbbaeabdadeaabbabbe
cebbebcaddaacccebeaeedababedeacdeaaaeeaecbe", "bddabdcae" 10582116
"
daacaedaceacabbaabdccdaaeaebacddadcaeaacadbceaecddecdeedcebcdacdaebccdeebcbd
eaccabcecbeeaadbccbaeccbbdaeadecabbbedceaddcdeabbcdaeadcddedddcececbeeabcbec
aeadddeddccbdbcdcbceabcacddbbcedebbcaccac", "ceadbaa" 8556153
"
babeceeacaadababaceacbcbdaeddedbbccddbdadaedbbccdbcaebecdacdedaaccaabecbbdcd
eececbcbebacbebdcbdbaebbabadbcdbbacddebcabaecdccecdbdcaddacecacada", "adebd"
262228
"
adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcd
dcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc", "
bcddceeeebecbc" 700531452
"
acdbccddceaaeaeacdacebbadacbacaccdabceeedcbccbecbeecbacbcceceebddcaabbcbddab
bededebbebcbdebedcddbabcbddcdddccdddcabddebbdecdcccacadbddddcdcbdbbaddabebee
bbcaebabbaebecabcceaabcdbceabde", "eadbec" 1887265
"
deccdbebedabedecedebeccdebbaddddecacdbdeaabebcbaaccaaeabcccccadbeaaecaecacdb
ebeeedbeeecedebcbeaaaaaecbbcdebeacabccabddadeecbacbcebbbceacddbbaccebabbadeb
ebcaaececbccac", "bbbdedc" 2081338
"
ddbeabacbdbddcaecdbeeaaabaecccaaddbdebccbbaeddaabbbccecaebccbeeecbeeeedbabca
edbcecadbeedddaeabdeeedea", "ecaaebeeedbba" 7259139
"
aaddbacbbcabdbceaeeaacbabbbaccacaacbabeddbedcdceceeabccabdadccceebcbcbecdbac
edcecdeadbaebceaedaaecbbebdecabbddccebaccabaaabbabceddceecadcccdceabbcdadbba
debdadeacbaddccdeebcddaebbcbedbd", "ccdeddeabb" 527764581
"
eacabdeadcbbddccdaccadddbaaebadcbaaedeeebdabbaeccdbcbaceaceddcdbddadecebaacd
cdaeeccaebaeebceaaaaaceaedd", "baaacbceabba" 1293119
"
ceddeeebbeceaeabcedeedabccdaaaecaddbceeeabadccbebeeacbeeeeeeebdbededeeeccbaa
edeacadccedbaacbbcaadeaedcbddddcbeaeaadcebabbeccdcebccbceeaedaee", "aeacbde"
2543265
"
xslledayhxhadmctrliaxqpokyezcfhzaskeykchkmhpyjipxtsuljkwkovmvelvwxzwieeuqnjo
zrfwmzsylcwvsthnxujvrkszqwtglewkycikdaiocglwzukwovsghkhyidevhbgffoqkpabthmqi
hcfxxzdejletqjoxmwftlxfcxgxgvpperwbqvhxgsbbkmphyomtbjzdjhcrcsggleiczpbfjcgtp
ycpmrjnckslrwduqlccqmgrdhxolfjafmsrfdghnatexyanldrdpxvvgujsztuffoymrfteholgo
nuaqndinadtumnuhkboyzaqguwqijwxxszngextfcozpetyownmyneehdwqmtpjloztswmzzdzqh
uoxrblppqvyvsqhnhryvqsqogpnlqfulurexdtovqpqkfxxnqykgscxaskmksivoazlducanrqxy
nxlgvwonalpsyddqmaemcrrwvrjmjjnygyebwtqxehrclwsxzylbqexnxjcgspeynlbmetlkacnn
bhmaizbadynajpibepbuacggxrqavfnwpcwxbzxfymhjcslghmajrirqzjqxpgtgisfjreqrqabs
sobbadmtmdknmakdigjqyqcruujlwmfoagrckdwyiglviyyrekjealvvigiesnvuumxgsveadrxl
pwetioxibtdjblowblqvzpbrmhupyrdophjxvhgzclidzybajuxllacyhyphssvhcffxonysahvz
hzbttyeeyiefhunbokiqrpqfcoxdxvefugapeevdoakxwzykmhbdytjbhigffkmbqmqxsoaiomgm
mgwapzdosorcxxhejvgajyzdmzlcntqbapbpofdjtulstuzdrffafedufqwsknumcxbschdybosx
krabyfdejgyozwillcxpcaiehlelczioskqtptzaczobvyojdlyflilvwqgyrqmjaeepydrcchfy
ftjighntqzoo", "rwmimatmhydhbujebqehjprrwfkoebcxxqfktayaaeheys" 543744000 |
z**q
发帖数: 41 | |
I***C
发帖数: 765 | 3 我用递归做的，小的test case都过了，大的test case运行时间过长。返不回答案，
哪位做过分享一下经验吧，谢谢
---------------------
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.
---------------------
method interface：
int numDistinct(string S, string T)
--------------------
Test cases
"
aabdbaabeeadcbbdedacbbeecbabebaeeecaeabaedadcbdbcdaabebdadbbaeabdadeaabbabbe
cebbebcaddaacccebeaeedababedeacdeaaaeeaecbe", "bddabdcae" 10582116
"
daacaedaceacabbaabdccdaaeaebacddadcaeaacadbceaecddecdeedcebcdacdaebccdeebcbd
eaccabcecbeeaadbccbaeccbbdaeadecabbbedceaddcdeabbcdaeadcddedddcececbeeabcbec
aeadddeddccbdbcdcbceabcacddbbcedebbcaccac", "ceadbaa" 8556153
"
babeceeacaadababaceacbcbdaeddedbbccddbdadaedbbccdbcaebecdacdedaaccaabecbbdcd
eececbcbebacbebdcbdbaebbabadbcdbbacddebcabaecdccecdbdcaddacecacada", "adebd"
262228
"
adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcd
dcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc", "
bcddceeeebecbc" 700531452
"
acdbccddceaaeaeacdacebbadacbacaccdabceeedcbccbecbeecbacbcceceebddcaabbcbddab
bededebbebcbdebedcddbabcbddcdddccdddcabddebbdecdcccacadbddddcdcbdbbaddabebee
bbcaebabbaebecabcceaabcdbceabde", "eadbec" 1887265
"
deccdbebedabedecedebeccdebbaddddecacdbdeaabebcbaaccaaeabcccccadbeaaecaecacdb
ebeeedbeeecedebcbeaaaaaecbbcdebeacabccabddadeecbacbcebbbceacddbbaccebabbadeb
ebcaaececbccac", "bbbdedc" 2081338
"
ddbeabacbdbddcaecdbeeaaabaecccaaddbdebccbbaeddaabbbccecaebccbeeecbeeeedbabca
edbcecadbeedddaeabdeeedea", "ecaaebeeedbba" 7259139
"
aaddbacbbcabdbceaeeaacbabbbaccacaacbabeddbedcdceceeabccabdadccceebcbcbecdbac
edcecdeadbaebceaedaaecbbebdecabbddccebaccabaaabbabceddceecadcccdceabbcdadbba
debdadeacbaddccdeebcddaebbcbedbd", "ccdeddeabb" 527764581
"
eacabdeadcbbddccdaccadddbaaebadcbaaedeeebdabbaeccdbcbaceaceddcdbddadecebaacd
cdaeeccaebaeebceaaaaaceaedd", "baaacbceabba" 1293119
"
ceddeeebbeceaeabcedeedabccdaaaecaddbceeeabadccbebeeacbeeeeeeebdbededeeeccbaa
edeacadccedbaacbbcaadeaedcbddddcbeaeaadcebabbeccdcebccbceeaedaee", "aeacbde"
2543265
"
xslledayhxhadmctrliaxqpokyezcfhzaskeykchkmhpyjipxtsuljkwkovmvelvwxzwieeuqnjo
zrfwmzsylcwvsthnxujvrkszqwtglewkycikdaiocglwzukwovsghkhyidevhbgffoqkpabthmqi
hcfxxzdejletqjoxmwftlxfcxgxgvpperwbqvhxgsbbkmphyomtbjzdjhcrcsggleiczpbfjcgtp
ycpmrjnckslrwduqlccqmgrdhxolfjafmsrfdghnatexyanldrdpxvvgujsztuffoymrfteholgo
nuaqndinadtumnuhkboyzaqguwqijwxxszngextfcozpetyownmyneehdwqmtpjloztswmzzdzqh
uoxrblppqvyvsqhnhryvqsqogpnlqfulurexdtovqpqkfxxnqykgscxaskmksivoazlducanrqxy
nxlgvwonalpsyddqmaemcrrwvrjmjjnygyebwtqxehrclwsxzylbqexnxjcgspeynlbmetlkacnn
bhmaizbadynajpibepbuacggxrqavfnwpcwxbzxfymhjcslghmajrirqzjqxpgtgisfjreqrqabs
sobbadmtmdknmakdigjqyqcruujlwmfoagrckdwyiglviyyrekjealvvigiesnvuumxgsveadrxl
pwetioxibtdjblowblqvzpbrmhupyrdophjxvhgzclidzybajuxllacyhyphssvhcffxonysahvz
hzbttyeeyiefhunbokiqrpqfcoxdxvefugapeevdoakxwzykmhbdytjbhigffkmbqmqxsoaiomgm
mgwapzdosorcxxhejvgajyzdmzlcntqbapbpofdjtulstuzdrffafedufqwsknumcxbschdybosx
krabyfdejgyozwillcxpcaiehlelczioskqtptzaczobvyojdlyflilvwqgyrqmjaeepydrcchfy
ftjighntqzoo", "rwmimatmhydhbujebqehjprrwfkoebcxxqfktayaaeheys" 543744000 |
z**q
发帖数: 41 | |
l*****a
发帖数: 559 | 5 递归版本的是这个吧。如果写得出递归的，dp版本的也该看得懂了。
int numDistinct(string S, string T) {
if(S.length() == 0)
return 0;
if(T.length() == 0)
return 1;
if(S.length() == 1 && T.length() == 1){
if(S[0] == T[0]) return 1;
else return 0;
}
if(S[0] != T[0]){
return numDistinct(S.substr(1), T);
}else{
return numDistinct(S.substr(1), T) + numDistinct(S.substr(1), T.
substr(1));
}
} |
p********2
发帖数: 123 | 6 OJ过了，字符串太长也可以用bigint
public class Solution {
public int numDistinct(String S, String T) {
// Start typing your Java solution below
// DO NOT write main() function
if(S.length()==0) return 0;
if(T.length()==0) return 1;
int[][] DP=new int[T.length()+1][S.length()+1];
for(int i=0;i<=T.length();i++){
DP[i][0]=0;
}
for(int i=0;i<=S.length();i++){
DP[0][i]=1;
}
for(int i=1;i<=T.length();i++){
for(int j=1;j<=S.length();j++){
if(S.charAt(j-1)==T.charAt(i-1)){
DP[i][j]=DP[i][j-1]+DP[i-1][j-1];
}
else
DP[i][j]=DP[i][j-1];
}
}
return DP[T.length()][S.length()];
}
} |
C***U
发帖数: 2406 | 7 你这楼好歪 哈哈
【在 z**q 的大作中提到】
: 正着写Dp就过了， 明天有面试，求Bless
|
s***u
发帖数: 101 | 8 DP的
int numDistinct(string S, string T) {
assert(T.size()>0);
if (!S.size()) return 0;
int n = S.size();
int m = T.size();
vector dp(m, 0);
for (int i=0; i
for (int j=m-1; j>=0; --j) {
if (T[j] == S[i]) {
if (j==0) dp[0]++;
else dp[j]+=dp[j-1];
}
}
}
return dp[m-1];
} |
f*********m
发帖数: 726 | 9 这步怎么理解？
if(S.charAt(j-1)==T.charAt(i-1)){
DP[i][j]=DP[i][j-1]+DP[i-1][j-1];
}
else
DP[i][j]=DP[i][j-1];
谢谢
【在 p********2 的大作中提到】
: OJ过了，字符串太长也可以用bigint
: public class Solution {
: public int numDistinct(String S, String T) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(S.length()==0) return 0;
: if(T.length()==0) return 1;
:
: int[][] DP=new int[T.length()+1][S.length()+1];
: for(int i=0;i<=T.length();i++){
|
f*********m
发帖数: 726 | |
|
|
l****o
发帖数: 315 | 11 如果当前字符相同，那有两种可能，用到和不用到这个字符，所以这两种情况加起来。
如果不同，那只能等于用不了这个字符的情况。
【在 f*********m 的大作中提到】
: 顶问题，期待回答，谢谢。
|
l*****a
发帖数: 559 | 12 递归版本的是这个吧。如果写得出递归的，dp版本的也该看得懂了。
int numDistinct(string S, string T) {
if(S.length() == 0)
return 0;
if(T.length() == 0)
return 1;
if(S.length() == 1 && T.length() == 1){
if(S[0] == T[0]) return 1;
else return 0;
}
if(S[0] != T[0]){
return numDistinct(S.substr(1), T);
}else{
return numDistinct(S.substr(1), T) + numDistinct(S.substr(1), T.
substr(1));
}
} |
p********2
发帖数: 123 | 13 OJ过了，字符串太长也可以用bigint
public class Solution {
public int numDistinct(String S, String T) {
// Start typing your Java solution below
// DO NOT write main() function
if(S.length()==0) return 0;
if(T.length()==0) return 1;
int[][] DP=new int[T.length()+1][S.length()+1];
for(int i=0;i<=T.length();i++){
DP[i][0]=0;
}
for(int i=0;i<=S.length();i++){
DP[0][i]=1;
}
for(int i=1;i<=T.length();i++){
for(int j=1;j<=S.length();j++){
if(S.charAt(j-1)==T.charAt(i-1)){
DP[i][j]=DP[i][j-1]+DP[i-1][j-1];
}
else
DP[i][j]=DP[i][j-1];
}
}
return DP[T.length()][S.length()];
}
} |
C***U
发帖数: 2406 | 14 你这楼好歪 哈哈
【在 z**q 的大作中提到】
: 正着写Dp就过了， 明天有面试，求Bless
|
s***u
发帖数: 101 | 15 DP的
int numDistinct(string S, string T) {
assert(T.size()>0);
if (!S.size()) return 0;
int n = S.size();
int m = T.size();
vector dp(m, 0);
for (int i=0; i
for (int j=m-1; j>=0; --j) {
if (T[j] == S[i]) {
if (j==0) dp[0]++;
else dp[j]+=dp[j-1];
}
}
}
return dp[m-1];
} |
f*********m
发帖数: 726 | 16 这步怎么理解？
if(S.charAt(j-1)==T.charAt(i-1)){
DP[i][j]=DP[i][j-1]+DP[i-1][j-1];
}
else
DP[i][j]=DP[i][j-1];
谢谢
【在 p********2 的大作中提到】
: OJ过了，字符串太长也可以用bigint
: public class Solution {
: public int numDistinct(String S, String T) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(S.length()==0) return 0;
: if(T.length()==0) return 1;
:
: int[][] DP=new int[T.length()+1][S.length()+1];
: for(int i=0;i<=T.length();i++){
|
f*********m
发帖数: 726 | |
l****o
发帖数: 315 | 18 如果当前字符相同，那有两种可能，用到和不用到这个字符，所以这两种情况加起来。
如果不同，那只能等于用不了这个字符的情况。
【在 f*********m 的大作中提到】
: 顶问题，期待回答，谢谢。
|
l*******0
发帖数: 63 | 19 哎，DP题目，总是每次想不出来。。。但是看过各位高手的思路后，又觉得懂了。。真
是弱爆了。。。 |
