Counting every way, not finding one
A match now offers a choice — use this letter or skip it — and both ways of counting add together. About 13 minutes.
How many ways can you spell it?
Take the word "rabbbit", with three b's, and ask: in how many different ways can you cross out letters to leave "rabbit"? You have to pick two of the three b's, so there are 3 ways.
Walk through the long word one letter at a time. Every letter can always be skipped: the ways that don't use it are still valid. When it matches the next letter you need, it can also be used, which opens up more ways.
A match adds, it doesn't choose
Here's the difference from earlier steps. When a letter matches, you don't choose between using it and skipping it. Both kinds of spelling really exist, so you add them together: the ways that skip this letter, plus the ways that use it as the match.
In the grid, "skip" is the box above and "use" is the box diagonally up-left. With three b's to choose two from, the count grows 1, 2, 3.
ways[i][j] = ways[i - 1][j] # skip this letter
Column 0: the empty t can be spelled exactly one way from anything (use nothing). Row 0: an empty s can't spell anything longer.
A letter matches. There are 3 ways to spell the target that skip this letter, and 2 ways that use it. How many ways in total?
- A5
- B3
- C2
Show the answer
5. Both kinds of spelling exist, so add them: 3 + 2 = 5.
Distinct subsequences
You get strings s and t. Return in how many different ways t can be spelled out by picking letters of s in order: the number of different sets of positions in s that read as t.
s = "rabbbit", t = "rabbit" → 3
0 ≤ s.length, t.length ≤ 1,000 · lowercase English letters · return a long