September 6Hard

Distinct subsequences

Dynamic Programming

Problem

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

The test cases are generated so that the answer fits on a 32-bit signed integer.

Solution

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        @cache
        def dp(i, j):
            if j == n:
                return 1
            if m - i < n - j:
                return 0
            res = 0
            for k in range(i, m):
                if s[k] == t[j]:
                    res += dp(k+1, j+1)
            return res
        return dp(0, 0)