Distinct Subsequences
Problem Description
Given two strings s and t, return the number of distinct subsequences of s which equals t.
The test cases are generated so that 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:
1 <= s.length, t.length <= 1000sandtconsist of English letters.
Solve it on LeetCode
Approaches
1. Recursive Solution
Intuition:
The basic idea is to recursively try to match each character of the string t with the characters in s. At each step, we have two choices: either take the character from s to match with the current character of t or skip the character from s. The base cases are defined when t becomes empty (which means we found a subsequence) or when s becomes empty without fully matching t.
Code:
- Time Complexity: O(2^m), where
mis the length ofs. The recursive tree can potentially explore all subsets ofs. - Space Complexity: O(n), where
nis the depth of the recursion stack, effectively the length ofs.
2. Memoization
Intuition:
The recursive solution contains overlapping subproblems. By storing the results of already computed states (i, j), we can avoid redundant calculations. This transforms the recursion into a top-down dynamic programming approach using a 2D array for memoization.
Code:
- Time Complexity: O(m * n), where
mis the length ofsandnis the length oftbecause each subproblem(i, j)is computed once. - Space Complexity: O(m * n) for the memoization table plus O(n) for the recursion stack.
3. Tabulation
Intuition:
Using a bottom-up approach, we can fill up a 2D table where dp[i][j] indicates the number of distinct subsequences of t[0...j-1] in s[0...i-1]. We initialize the first row and first column based on the base conditions and progressively fill the DP table.
Code:
- Time Complexity: O(m * n), where
mis the length ofsandnis the length oft. - Space Complexity: O(m * n) for the table.
4. Optimized Tabulation
Intuition:
Since at every step we only use the current and previous rows, we can optimize space by maintaining only two rows at a time. Swapping rows reduces space complexity from O(m*n) to O(n).
Code:
- Time Complexity: O(m * n), where
mis the length ofsandnis the length oft. - Space Complexity: O(n) for storing two rows.