115. Distinct Subsequences

发表于 | 分类于

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

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

Here is an example:
S = “rabbbit”, T = “rabbit”

Return 3.

解法1：O(NM)

dp[i][j]表示的是s[0,i]和t[0,j]的匹配答案。
递推关系可以分为s[i] == t[j] 和不等的两种情况
如果相等，那么既可以是包括i, 那么就是需要知道(i-1,j-1)的结果；也可以是不包括j, 那么就需要知道(i -1, j)的结果
如果不相等，只要(i - 1, j)就可以了。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int numDistinct(String s, String t) {
        int n = s.length();
        int m = t.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][m];
    }
}