Distinct Subsequences

30% Accepted

Given a string S and a string T, count the number of distinct subsequences of T in S.

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).

Have you met this question in a real interview? Yes
Example
Given S = "rabbbit", T = "rabbit", return 3.

Challenge

• Do it in O(n2) time and O(n) memory.
• O(n2) memory is also acceptable if you do not know how to optimize memory.

Tags Expand

• String
• Dynamic Programming

O(n2) memory 思路

• Two Sequence DP
• 很好的解释
• 仔细理解题意，题目意思不是很明确
• 画图找规律，直接看不到规律就自己凑规律，其实都是数学原理
• 画出矩阵型的图去找规律匹配

题意理解

Since you can choose two b from three and there are total of 3 choices, i.e.,

the first and the second
the first and the third
the second and the third


    r a b b b i t
  1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
从这个表可以看出，无论T的字符与S的字符是否匹配，dp[i][j] = dp[i][j - 1].
就是说，假设S已经匹配了j - 1个字符，得到匹配个数为dp[i][j - 1].
现在无论S[j]是不是和T[i]匹配，匹配的个数至少是dp[i][j - 1]。
除此之外，当S[j]和T[i]相等时，我们可以让S[j]和T[i]匹配，然后让S[j - 1]和T[i - 1]去匹配。
所以递推关系为：
dp[0][0] = 1; // T和S都是空串.
dp[0][1 ... S.length() - 1] = 1; // T是空串，S只有一种子序列匹配。
dp[1 ... T.length() - 1][0] = 0; // S是空串，T不是空串，S没有子序列匹配。
dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0).1 <= i <= T.length(), 1 <= j <= S.length()

public class Solution {
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
    public int numDistinct(String S, String T) {
        // write your code here
        int[][] ret = new int[S.length()+1][T.length()+1];
        for (int i = 0 ; i <= T.length(); i++) {
            ret[0][i] = 0;
        }
        for (int i = 0 ; i <= S.length(); i++) {
            ret[i][0] = 1;
        }
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= T.length(); j++) {
                if (i < j) {
                    ret[i][j] = 0;
                    continue;
                }
                if (S.charAt(i - 1) != T.charAt(j - 1)) {
                    ret[i][j] = ret[i - 1][j];
                } else {
                    ret[i][j] = ret[i-1][j-1] + ret[i-1][j];
                }
            }
        }

        return ret[S.length()][T.length()];
    }
}

O(n) memory 优化

public class Solution {
    /*
    bbb bb
    state:
    dp[i][j], first i chars of S and first j chars of T, how many distinct subsequences

    function:
    if(s.charAt(i) == s.charAt(j))
    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
    else
    dp[i][j] = dp[i - 1][j]
    initialization:
    dp[i][0] = 0;
    dp[0][j] = 0;

    answer:
    dp[m][n]
    */
    public int numDistinct(String s, String t) {
        if (s == null || t == null) {
            return 0;
        }
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[2][n + 1];
        // for (int i = 0; i <=m; i++) {
        //     dp[i][0] = 1;
        // }
        dp[0][0] = 1;
        dp[1][0] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= Math.min(i, n); j++) {
                char schar = s.charAt(i - 1);
                char tchar = t.charAt(j - 1);
                if (schar == tchar) {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + dp[(i - 1) % 2][j];
                } else {
                    dp[i % 2][j] = dp[(i - 1) % 2][j];
                }
            }
        }
        return dp[m % 2][n];
    }
}