#115

Distinct Subsequences

candidate master · 1380 · lc hard +32 · verified · 51.6% accepted · 7,374 likes · top 41%

⚑ String Matching DP (LCS / Edit Distance)

Description

Count the number of distinct ways that string s contains string t as a subsequence, and return that count.

Inputs are guaranteed to produce an answer that fits within a 32-bit signed integer.

Example 1:

Input: s = "rabbbit", t = "rabbit"

Output: 3

Explanation:

As shown below, there are 3 ways you can generate "rabbit" from s.

rabbbit

Example 2:

Input: s = "babgbag", t = "bag"

Output: 5

Explanation:

As shown below, there are 5 ways you can generate "bag" from s.

babgbag

Code

1

2

3

class Solution:
    def numDistinct(self, s: str, t: str) -> int:

class Solution:
    def numDistinct(self, s: str, t: str) -> int: