Distinct Subsequences - Hard Python 2-D Dynamic Programming Interview Problem

Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string is a subsequence of another string if it can be formed by deleting some (possibly zero) characters from the original string without changing the relative order of the remaining characters.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation: There are 3 ways to pick characters from "rabbbit" to form "rabbit":
  rabb_bit -> rabbit (skip 3rd b)
  rab_bbit -> rabbit (skip 2nd b)
  ra_bbbit -> rabbit (skip 1st b)

Example 2

Input: s = "babgbag", t = "bag"
Output: 5
Explanation: There are 5 distinct ways to choose b, a, g from "babgbag" in order.

Constraints

1 <= s.length, t.length <= 1000
s and t consist of English lowercase letters

Hints