Loading problem…
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: "rabbbit" has three b's, and "rabbit" needs two of them. There are 3 ways to choose two of the three b's while keeping every other letter, so the answer is 3.
Example 2
Input: s = babgbag, t = bag
Output: 5
Explanation: "bag" can be formed from "babgbag" in 5 ways, using different combinations of b, a and g positions: (0,1,3), (0,1,6), (0,5,6), (2,5,6) and (4,5,6).
Example 3
Input: s = abc, t = abc
Output: 1
Explanation: The strings are identical, so there is exactly one way: use every character.
dp[i][j] counts how many subsequences of the first i chars of s equal the first j chars of t. You can always skip s[i-1]; if it matches t[j-1] you may also use it.
Run checks all cases above. Submit evaluates all test cases.