Distinct Subsequences
You are given two strings s and t, both consisting of english letters.
Return the number of distinct subsequences of s which are equal to t.
Example 1:
Input: s = "caaat", t = "cat"
Output: 3Explanation: There are 3 ways you can generate "cat" from s.
- (c)aa(at)
- (c)a(a)a(t)
- (ca)aa(t)
Example 2:
Input: s = "xxyxy", t = "xy"
Output: 5Explanation: There are 5 ways you can generate "xy" from s.
- (x)x(y)xy
- (x)xyx(y)
- x(x)(y)xy
- x(x)yx(y)
- xxy(x)(y)
Constraints:
1 <= s.length, t.length <= 1000sandtconsist of English letters.
Recommended Time & Space Complexity
You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the length of the string s and n is the length of the string t.
Hint 1
Try to think in terms of recursion and visualize it as a decision tree, as we need to explore all subsequences of s. Can you determine the possible decisions at each recursion step?
Hint 2
We recursively iterate through the strings using indices i and j for s and t, respectively. At each recursion step, we can either skip the current character of s or include it in the current path if it matches the current character of t. Can you determine the base conditions for this recursive function?
Hint 3
If index j goes out of bounds, we return 1 as a valid subsequence is found. If index i goes out of bounds first, we return 0. At each recursion step, we return the sum of both paths. This approach is exponential. Can you think of a way to optimize it?
Hint 4
We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a 2D array can be used to store these results.