Distinct Subsequences Problem


Description

LeetCode Problem 115.

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

The test cases are generated so that the answer fits on a 32-bit signed integer.

Example 1:

1
2
3
4
5
6
7
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:

1
2
3
4
5
6
7
8
9
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:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	// Define dp[i][j] to be the number of distinct subsequences 
	// of t[0..i - 1] in s[0..j - 1]. Then we have the following state equations:
	// General case 1: dp[i][j] = dp[i][j - 1] if t[i - 1] != s[j - 1];
	// General case 2: dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] if t[i - 1] == s[j - 1];
	// Boundary case 1: dp[0][j] = 1 for all j;
	// Boundary case 2: dp[i][0] = 0 for all positive i.
    int numDistinct(string s, string t) {
        int m = t.length(), n = s.length();
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
        for (int j = 0; j <= n; j++) dp[0][j] = 1;
        for (int j = 1; j <= n; j++)
            for (int i = 1; i <= m; i++)
                dp[i][j] = dp[i][j - 1] + (t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] : 0);
        return dp[m][n];
    }
};  




Related Posts

Best Time To Buy And Sell Stock With Cooldown Problem

LeetCode 309. You are given an array prices where prices[i]...

Maximum Product Subarray Problem

LeetCode 152. Given an integer array nums, find a contiguous...

House Robber Problem

LeetCode 198. You are a professional robber planning to rob...

Dungeon Game Problem

LeetCode 174. The demons had captured the princess and imprisoned...

Best Time To Buy And Sell Stock IV Problem

LeetCode 188. You are given an integer array prices where...

Palindrome Partitioning II Problem

LeetCode 132. Given a string s, partition s such that...