Posted on 2013-04-26 23:33
小明 阅读(2017)
评论(1) 编辑 收藏 所属分类:
数据结构和算法
分析：
解法一：递归
直觉的解法是使用递归，先在S中找到T的第一个字符，然后递归查找在剩余的S查找剩余的T（除去首字符）。
如果T的长度为1，只需要计算S中一共有几个T就可以了。
代码如下，非常简洁，但是效率不高：
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(m,n)为S的子串(0..m)中子序列为T(0..n)的个数。
那么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)
代码如下：复杂度为O(mn) m,n为S和T的长度
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];
}