public class Solution {
// state: f[i][j] - number of distinct subsequence of T.substring(0, j] in S.substring(0, i]
// function: f[i][j] = f[i - 1][j] + (f[i - 1][j - 1], if T[j] == S[i]) // Attn!
// initialize: f[i][0] = 1
// result f[T.length()][S.length()]
public int numDistinct(String s, String t) {
if (s == null || t == null || s.length() == 0 || t.length() == 0) {
return 0;
}
int[][] f = new int[s.length() + 1][t.length() + 1];
for (int i = 0; i <= s.length(); i++) {
f[i][0] = 1;
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= t.length(); j++) {
f[i][j] = f[i - 1][j];
if (t.charAt(j - 1) == s.charAt(i - 1)) {
f[i][j] += f[i - 1][j - 1];
}
}
}
return f[s.length()][t.length()];
}
}
http://www.cs.cmu.edu/~yandongl/distinctseq.html
没有评论:
发表评论