Python O(2*n) space


  • 0
    S
    class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        m, n = len(s), len(t)
        prev = [1]+[0]*n
        for i in range (1, m+1):
            cur = [1]
            for j in range (1, n+1):
                if s[i-1] == t[j-1]:
                    cur.append(prev[j]+prev[j-1])
                else:cur.append(prev[j])
            prev = cur
        return prev[-1]

Log in to reply
 

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