Python DP (LCS)


  • 0
    Y
        def minDistance(self, A, B):
            """
            :type A: str
            :type B: str
            :rtype: int
            """
            m,n=len(A),len(B)
    
            dp=[[0 for _ in xrange(n+1)] for _ in xrange(m+1)]
    
            for i in xrange(1,m+1):
                for j in xrange(1,n+1):
                    if A[i-1]==B[j-1]:
                        dp[i][j]=dp[i-1][j-1]+1
                    else:
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            res=m-dp[m][n]+n-dp[m][n]
            return res
    

Log in to reply
 

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