# Solution using DP in python, time: O(mn), space:O(mn)

• explanation:

1. Regarding the problem `(i,j)` (i.e. comparing `word1[:i+1]` and `word2[:j+1]`) , the directly related subproblems are namely `(i-1,j-1), (i,j-1),(i-1,j)`, each of them can be calculated within a right-down direction in a `n*m` matrix. This is the big picture.
2. How to construct the solution of problem `(i,j)` with the solution of `(i-1,j-1), (i,j-1),(i-1,j)`? The allowed operations are replacing, deleting and adding one character. Thus, if the current characters under comparing (say `word1[i]` and `word2[j]` ),
There are 2 cases:
Case 1. if they are equal, the solution of `(i,j)` is the same as `(i-1,j-1)`.
Case 1 solution: `dp[i][j]=dp[i-1][j-1]`
Case 2. if they are not equal, we can either add/delete 1 letter (both are 1 operation cost) based on solution `(i-1,j),(i,j-1)` or delete (1 operation) or replace `word1[i]` with `word2[j]`, vice versa.
Case 2 solution: `dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1],[j])+1`

code:

``````class Solution:
def minDistance(self, word1, word2):
if word1==word2:
return 0
m,n=len(word1)+1,len(word2)+1
dp=[[0 for i in range(n)] for j in range(m)]
for i in range(m):
dp[i][0]=i
for j in range(n):
dp[0][j]=j

for i in range(1,m):
for j in range(1,n):
if word1[i-1]==word2[j-1]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
return dp[m-1][n-1]
``````

Any improving advice is appreciated :)

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