2016年8月10日星期三

[LeetCode] #115 Distinct Subsequences


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

没有评论:

发表评论