Python, Straightforward with Explanation

  • 3

    Let dp(i, j) be the answer for strings A[i:] and B[j:]. Let's try to compute it by a top-down dp:

    • When i == len(A) or j == len(B), one of the strings is empty, so the answer is just the sum of the remaining lengths.
    • When A[i] == B[j], the answer is just dp(i+1, j+1). For example, when evaluating the distance between "acai" and "apple", we only need to look at the distance between "cai" and "pple".
    • When A[i] != B[j], then they both cannot be in the final word, so we either delete A[i] or B[j]. Thus, our answer is 1 + min(dp(i+1, j), dp(i, j+1)).
    def minDistance(self, A, B):
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if i == len(A) or j == len(B):
                    ans = len(A) + len(B) - i - j
                elif A[i] == B[j]:
                    ans = dp(i+1, j+1)
                    ans = 1 + min(dp(i+1, j), dp(i, j+1))
                memo[i, j] = ans
            return memo[i, j]
        return dp(0, 0)

    We could have also attempted a bottom-up DP, as shown below.

    def minDistance(self, A, B):
        M, N = len(A), len(B)
        dp = [[0] * (N+1) for _ in xrange(M+1)]
        for i in xrange(M):
            dp[i][-1] = M-i
        for j in xrange(N):
            dp[-1][j] = N-j
        for i in xrange(M-1, -1, -1):
            for j in xrange(N-1, -1, -1):
                if A[i] == B[j]:
                    dp[i][j] = dp[i+1][j+1]
                    dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1])
        return dp[0][0]

Log in to reply

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