The problem
Given strings s and t, return the number of different ways to pick characters of s, in order, that spell t. Picks that use different positions count separately.
Examples
- Input
s = "rabbbit", t = "rabbit"
- Output
3
- Input
s = "babgbag", t = "bag"
- Output
5
Constraints
- 1 ≤ s.length, t.length ≤ 1000
- English letters only.
- The answer fits in a 32-bit signed integer.
The idea
Read s one letter at a time, keeping ways[j]: the number of ways to spell the first j letters of t from what has been read. Each new letter can be skipped — every count stays — or, if it equals t’s j-th letter, used to finish a copy of t[0..j), adding ways[j − 1].
Update j from high to low, so the letter just read is not used twice. The empty prefix of t is spelled exactly one way. The intermediate counts can outgrow 32 bits even when the answer does not; since only additions are involved, counting modulo 2³² still ends on the exact answer.
- Time
- O(m · n)
- Space
- O(n)
Solution · every language run against every case
class Solution: def numDistinct(self, s: str, t: str) -> int: # ways[j]: ways to pick t[:j] from the part of s read so far. Each new letter of s can # either be skipped, or — if it equals t[j - 1] — end a copy of t[:j]. ways = [1] + [0] * len(t) # the empty t is picked one way for ch in s: for j in range(len(t), 0, -1): # downwards, so this letter is used once if t[j - 1] == ch: ways[j] += ways[j - 1] return ways[len(t)]