05 August 2008
给一个s和t，在s中找到所有与t相同的subsequences(不连续)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int numDistinct(String S, String T) {
// array creation
int[][] mem = new int[T.length()+1][S.length()+1];
// filling the first row: with 1s
for(int j=0; j<=S.length(); j++) {
mem[0][j] = 1;
}
// the first column is 0 by default in every other rows but the first, which we need.
for(int i=0; i<T.length(); i++) {
for(int j=0; j<S.length(); j++) {
if(T.charAt(i) == S.charAt(j)) {
mem[i+1][j+1] = mem[i][j] + mem[i+1][j];
} else {
mem[i+1][j+1] = mem[i+1][j];
}
}
}
return mem[T.length()][S.length()];
}