explanation:

- 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. - 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 :)