Description

Given a stringSand a stringT, count the number of distinct subsequences ofTinS.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,"ACE"is a subsequence of"ABCDE"while"AEC"is not).

Example

Given S ="rabbbit", T ="rabbit", return3.

Solution

状态方程dp[i][j] = dp[i][j - 1] + (dp[i - 1][j - 1] if char[i] == char[j])
初始状态dp[i][0] = 1
特殊状态s.length() > 0 && t.length() == 0 return 1;

public class Solution {
    /*
     * @param : A string
     * @param : A string
     * @return: Count the number of distinct subsequences
     */
    public int numDistinct(String S, String T) {
        // write your code here
        if (S == null || T == null || S.length() == 0) {
            return 0;
        }

        if (S.length() < T.length()) {
            return 0;
        }

        if (T.length() == 0) {
            return 1;
        }

        int lens = S.length();
        int lent = T.length();
        int[][] dp = new int[lens + 1][lent + 1];
        for (int i = 0; i <= lens; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= lens; i++) {
            for (int j = 1; j <= lent; j++) {
                dp[i][j] = dp[i - 1][j];
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return dp[lens][lent];
    }
};