#115

Distinct Subsequences

hard· 2-D DPruns: 0

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 by deleting some characters without changing the relative order of the remaining characters. The test cases are generated so the answer fits in a 32-bit integer.

wpm 0acc 100%time 0:000 / 508

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

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.