Count the ways to pick letters of s, in order, that spell t: each letter is skipped or used, and a table adds up both choices.
▼The problem
LeetCode 115 (Hard). Given strings s and t, return the number of distinct subsequences of s that equal t (the number of ways to pick positions of s, in order, that spell t).
Examples (LeetCode's): s = "rabbbit", t = "rabbit" → 3 (drop any one of the three b's) and s = "babgbag", t = "bag" → 5.
The solution
def num_distinct(s, t):
dp = [1] + [0] * len(t)
for ch in s:
for j in range(len(t), 0, -1):
if ch == t[j - 1]:
dp[j] += dp[j - 1]
return dp[-1]Transcript
Distinct Subsequences. Given strings s and t, count the ways to pick letters from s, in order, that spell t.
In rabbbit, drop any one of the three b's to get rabbit: three ways. And babgbag holds bag five ways.
The slow way: try every subsequence of s and count the matches. Each letter is in or out, so that's two to the n: here, one hundred twenty-eight.
The key idea: walk through s, and at each letter, skip it or use it. Let dp of i, j be the ways the first i letters of s spell the first j of t. Skipping keeps the count from the left. Using a matching letter adds the count up and to the left. An empty t has one way. It's the Longest Common Subsequence grid, counting ways instead of taking a max.
In code, keep one row, starting with a one for the empty prefix. For each letter of s, sweep t from right to left, and where the letters match, add the count before it. Return the last cell.
On babgbag, each b starts a new way: one, then two. The first g completes one bag. The third b makes three. The next a joins all three b's, so b a grows to four. The last g adds those four to the one: five.
That's s times t steps of constant work, and one row of space. Right to left keeps each letter from being used twice.
Skip it or use it, add the ways, sweep from the right. That's Distinct Subsequences.