Given strings s and t, return the number of distinct subsequences of s that equal t.
dp[i][j] = ways the first i chars of s form the first j chars of t. dp[i][j] = dp[i−1][j] (ignore s[i−1]) + dp[i−1][j−1] when s[i−1] = t[j−1].
1function numDistinct(s: string, t: string): number {2const dp = Array.from({ length: s.length + 1 }, () => new Array(t.length + 1).fill(0));3for (let i = 0; i <= s.length; i++) dp[i][0] = 1;4for (let i = 1; i <= s.length; i++)5for (let j = 1; j <= t.length; j++)6dp[i][j] = dp[i - 1][j] + (s[i - 1] === t[j - 1] ? dp[i - 1][j - 1] : 0);7return dp[s.length][t.length];8}
| ∅ | r | a | b | b | i | t | |
|---|---|---|---|---|---|---|---|
| ∅ | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| r | 1 | ||||||
| a | 1 | ||||||
| b | 1 | ||||||
| b | 1 | ||||||
| b | 1 | ||||||
| i | 1 | ||||||
| t | 1 |
Empty t can be formed one way; non-empty t from empty s in zero ways.
Space: play/pause · ←/→: step