Python time O(m*n) space O(n) beat 95%

  • 0

    Same idea as top posted solution only with simplified logic. 2D dp list -> 1D dp list.

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

Log in to reply

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