Given two strings s and t, count how many different subsequences of s are equal to t. Two subsequences are different if they use a different set of positions in s. The final answer fits in a 32-bit signed integer.
b characters can be used, giving 3 ways.- 1 <= s.length, t.length <= 1000
- `s` and `t` have English letters
- The answer fits in a 32-bit signed integer
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force enumerates all 2^n subsequences of s and counts the matches. Instead, build the count up. State: dp[i][j] is the number of ways the first i characters of s can form the first j characters of t. Recurrence: we can always skip s[i-1], which gives dp[i-1][j]. If s[i-1] == t[j-1], we can also match them, which adds dp[i-1][j-1]. Base case: dp[i][0] = 1 (choose nothing) and dp[0][j] = 0 for j > 0. With one 1D array, loop j from right to left so dp[j-1] still holds the previous row.
Algorithm
- Create
dpof sizelen(t) + 1withdp[0] = 1and the rest 0. - For each character
cofs, loopjfromlen(t)down to 1. - If
c == t[j-1], dodp[j] += dp[j-1]. - Return
dp[len(t)].
O(|s| * |t|)Space: O(|t|)unsigned long long, whose wrap around is well defined; additions modulo 2^64 still give the correct final answer.class Solution: def numDistinct(self, s: str, t: str) -> int: n = len(t) dp = [0] * (n + 1) dp[0] = 1 # empty t can be formed in one way for c in s: # right to left so dp[j - 1] still belongs to the previous row for j in range(n, 0, -1): if c == t[j - 1]: dp[j] += dp[j - 1] return dp[n]