# Python, Straightforward with Explanation

• 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)
else:
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]
else:
dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1])

return dp[0][0]
``````

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