Distinct Subsequences LeetCode solution in Python

1
# Runtime: 1092 ms (Top 41.44%) | Memory: 70.6 MB (Top 63.39%)
2
class Solution:
3
    def numDistinct(self, s: str, t: str) -> int:
4
        if len(t) > len(s):
5
            return 0
6
        ls, lt = len(s), len(t)
7
        res = 0
8
        dp = [[0] * (ls + 1) for _ in range(lt + 1)]
9
        for j in range(ls + 1):
10
            dp[-1][j] = 1
11
        for i in range(lt - 1, -1, -1):
12
            for j in range(ls - 1, -1, -1):
13
                dp[i][j] = dp[i][j + 1]
14
                if s[j] == t[i]:
15

16
                    dp[i][j] += dp[i + 1][j + 1]
17
        return dp[0][0]