Several Python Solutions


  • 0

    First, the naive solution with memo, AC in 1250~ms, pretty slow right?

    class Solution(object):
        def numDistinct(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: int
            """
            def helper(i, j):
                if j == n2: return 1
                if (i, j) not in memo:
                    memo[(i, j)] = sum(helper(k+1, j+1) for k in range(i, n1) if s[k] == t[j])
                return memo[(i, j)]
    
            n1, n2 = len(s), len(t)
            memo = {}
            return helper(0, 0)
    

    Let's try 2D DP. This one use O(m*n) space and AC in 250~ms.

    class Solution(object):
        def numDistinct(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: int
            """
            n1, n2 = len(s), len(t)
            dp = [[1] * (n2+1) for i in range(n1+1)]
            for j in range(1, n2+1):
                dp[0][j] = 0
            for i in range(1, n1+1):
                for j in range(1, n2+1):
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (s[i-1] == t[j-1])
            return dp[-1][-1]
    

    As always, 2D DP can be converted into 1D DP mostly. This one use O(n) space and AC in 200~ms.

    class Solution(object):
        def numDistinct(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: int
            """
            n1, n2 = len(s), len(t)
            dp = [1] + [0] * n2
            for i in range(1, n1+1):
                pre = dp[0]
                for j in range(1, n2+1):
                    dp[j], pre = dp[j] + pre * (s[i-1] == t[j-1]), dp[j]
            return dp[-1]
    

Log in to reply
 

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