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.
Java
Distinct Subsequences
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
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])