Distinct Subsequences
Hard · dynamic programming
A message arrives as a long string of letters, source. You are looking for a shorter word hidden inside it.
You can spell word by choosing some positions in source, from left to right, and reading the letters at those positions in order. Skipped letters are simply ignored. Two ways count as different if they use a different set of positions, even when the letters read are the same.
Return the number of different ways to spell word. If it cannot be spelled at all, return 0.
The answer is guaranteed to fit in a signed 32-bit integer.
Examples
Example 1
Input: source = "aabb", word = "ab"
Output: 4
Pick either a (positions 0 or 1) and either b (positions 2 or 3): 2 x 2 = 4 different ways.
Example 2
Input: source = "bananas", word = "ban"
Output: 3
The b is at position 0. The a at position 1 can pair with the n at 2 or at 4, and the a at position 3 only with the n at 4. That is 3 ways.
Example 3
Input: source = "abc", word = "abcd"
Output: 0
The word is longer than the source, so it cannot be spelled.
Constraints
- 1 <= len(source), len(word) <= 500
- Both strings contain only lowercase English letters.
- The answer fits in a signed 32-bit integer.