Given two strings s and t, return the number of distinct subsequences of s which equals t. A subsequence of a string is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.
30:00
Java
Distinct Subsequences
hard
Topics
Companies
Given two strings s and t, return the number of distinct subsequences of s which equals t. A subsequence of a string is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.
Example 1:
Input: {"s":"rabbbit","t":"rabbit"}
Output: 3
Constraints:
1≤s.length,t.length≤1000
s and t consist of English letters.
Input
arr ={"s":"rabbbit","t":"rabbit"}
Initialize DP table. dp[i][0] = 1 (empty t matches any prefix).
s:
r
a
b
b
b
i
t
t:
r
a
b
b
i
t
DP Table (dp[i][j] = ways to form t[0..j-1] from s[0..i-1])