[LeetCode] 115. Distinct Subsequences

Given two strings s and t, return the number of distinct subsequences of s which equals t.

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

It is guaranteed the answer fits on a 32-bit signed integer.

Example 1:
Input: s = “rabbbit”, t = “rabbit”
Output: 3
Explanation:
As shown below, there are 3 ways you can generate “rabbit” from S.
rabbbit
rabbbit
rabbbit

Example 2:
Input: s = “babgbag”, t = “bag”
Output: 5
Explanation:
As shown below, there are 5 ways you can generate “bag” from S.
babgbag
babgbag
babgbag
babgbag
babgbag

Constraints:

• 0 <= s.length, t.length <= 1000
• s and t consist of English letters.

不同的子序列。

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/distinct-subsequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是二维DP。我们首先创建一个二维数组，长度是 int[][] dp = new int[s.length() + 1][t.length() + 1]。+1 的部分是DP类型的题的经典操作，这个DP数组的含义是当 S 以 i 结尾，T 以 j 结尾的时候，满足题意的 subsequence 的个数是多少。

这里有几个重点需要提及

• 首先如果 T 为空的时候，因为一个空串是任何非空字符串的 subsequence 所以 dp[i][0] = 1
• 如果 T 不为空，又分如下两种情况，我们用这个例子理解，S = ABCC, T = ABC
  如果s.charAt(i - 1) == t.charAt(j - 1)，也就是两边字母相同的时候，dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]。比如例子中如果S和T都走到了各自最后的字母C的时候，这里有匹配，需要比较的是ABCC中含有多少个不同的ABC，这里分两种情况
  • 如果我们考虑使用当前这个匹配，我们看一下前面的子串 ABC 和 AB 的匹配情况，对应dp[i - 1][j - 1]
  • 如果不使用当前这个匹配，也就是说 S 中不包含标红的 C 的时候，我们看一下 S = ABC 里面有多少能有多少subsequence能匹配 T，对应dp[i - 1][j]
• 把如上这两种情况加起来，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
  如果s.charAt(i - 1) != t.charAt(j - 1)，也就是当前字母不匹配的情况下，我们只需要看 dp[i][j - 1]

复杂度

时间O(mn)
空间O(mn)

代码

Java实现

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化：空串匹配
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[m][n];
    }
}