Posted on 2013-04-26 23:33
小明 閱讀(2047)
評(píng)論(1) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法
分析：
解法一：遞歸
直覺的解法是使用遞歸，先在S中找到T的第一個(gè)字符，然后遞歸查找在剩余的S查找剩余的T（除去首字符）。
如果T的長(zhǎng)度為1，只需要計(jì)算S中一共有幾個(gè)T就可以了。
代碼如下，非常簡(jiǎn)潔，但是效率不高：
public int numDistinct(String S, String T) {
int ls = S.length();
int lt = T.length();
if(ls<lt){
return 0;
}
char[] cs = S.toCharArray();
char t0 = T.charAt(0);
String T1 = T.substring(1);
int result = 0;
for(int i=0;i<ls;++i){
if(cs[i]==t0){
if(lt>1){
result += numDistinct(S.substring(i+1),T1);
}
else{
++result;
}
}
}
return result;
}
解法二，
為了提高效率，很自然的想法是使用動(dòng)態(tài)規(guī)劃，記錄中間狀態(tài)，從而避免重復(fù)計(jì)數(shù)。
狀態(tài)轉(zhuǎn)移方程如下，計(jì)D(m,n)為S的子串(0..m)中子序列為T(0..n)的個(gè)數(shù)。
那么D(m,n) = D(m-1,n) if S(m)<>T(n)
= D(m-1,n)+D(m-1,n-1) if (S(m)=T(n) and n>0)
= D(m-1,n)+1 if(S(m)=T(0) and n=0)
代碼如下：復(fù)雜度為O(mn) m,n為S和T的長(zhǎng)度
public int numDistinct(String S, String T) {
int ls = S.length();
int lt = T.length();
if(ls<lt){
return 0;
}
int[][] memo = new int[ls][lt];
char[] cs = S.toCharArray();
char[] ct = T.toCharArray();
memo[0] = new int[lt];
memo[0][0]= (cs[0]==ct[0])?1:0;
for(int i=1;i<ls;++i){
int[] mprev = memo[i-1];
int[] m = memo[i] = new int[lt];
char s = cs[i];
for(int j=0;j<lt;++j){
char t = ct[j];
m[j] = mprev[j];
if(s==t){
m[j] += ((j==0)?1:mprev[j-1]);
}
}
}
return memo[ls-1][lt-1];
}