5 lines python DP

  • 1
    class Solution(object):
        def numDistinct(self, s, t):
            dp = [[1] * (len(s)+1)] + [[0] * (len(s)+1) for y in range(len(t))]
            for j in range(1, len(t)+1):
                for i in range(1, len(s)+1):
                    dp[j][i] += dp[j-1][i-1] + dp[j][i-1] if s[i-1] == t[j-1] else dp[j][i-1]
            return dp[-1][-1]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.