Description
Given two strings s and t, return the number of distinct subsequences of s which equals t. A subsequence is a sequence derived by deleting some characters without changing order.
Examples
Input:
s = "rabbbit", t = "rabbit"Output:
3Explanation:
There are 3 ways to generate 'rabbit' from 'rabbbit'.
Input:
s = "aaa", t = "aa"Output:
3Explanation:
There are 3 ways to generate 'aa' from 'aaa': use positions (0,1), (0,2), or (1,2). This demonstrates how multiple identical characters create multiple valid subsequences.
Input:
s = "computer", t = "cut"Output:
1Explanation:
There is only 1 way to generate 'cut' from 'computer': c(0) + u(4) + t(7). Each required character appears exactly once in the correct order, so there's only one possible subsequence.
Constraints
- •
1 ≤ s.length, t.length ≤ 1000 - •
s and t consist of English letters.