Distinct Subsequences
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.
Examples
Input: ["rabbbit","rabbit"]
Output: 3
Input: ["babgbag","bag"]
Output: 5
Hints
Consider using a 2D dynamic programming table where `dp[i][j]` represents the number of ways to form the first `j` characters of `t` using the first `i` characters of `s`.
To optimize space, observe that each row of the DP table only depends on the previous row. Implement a space-optimized version using a 1D array and a temporary variable to store the diagonal value.
Analyze the time and space complexity of your solution. Can you further optimize the space complexity to O(min(m, n)) where m and n are the lengths of `s` and `t` respectively?
Related Problems
Distinct Subsequences
Given two strings `s` and `t`, return the number of distinct subsequences of `s` which equals `t`.