DiffPush Tier Dynamic Programming · DP on Strings O(n*m) · O(m)
A lighthouse emits a long pulse string, and the coast guard hunts for one short distress code as a subsequence of those pulses. Multiple flashes can serve the same slot, so the same code may hide in the beam log many different ways. The monitoring console counts every distinct embedding of the code in the log.
Input: Two strings s (the log) and t (the code).
Output: Return the number of distinct subsequences of s that equal t.
1 <= len(s), len(t) <= 1000strings consist of English lettersInput: {"s":"rabbbit","t":"rabbit"}
Output: 3
Any one of the three 'b's in the log can be dropped while spelling "rabbit".
Input: {"s":"babgbag","t":"bag"}
Output: 5
Five distinct position combinations spell "bag" in order.