```
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
## Longest Common Subsequence
## dp[i][j] = 0, if len(word1) == 0 or len(word2)==0
## = dp[i-1][j-1]+1, if word1[i] == word2[j]
## = max(dp[i-1][j], dp[i][j-1])
dp = [[0 for col in range(len(word2)+1)] for row in range(len(word1)+1)]
for i in range(len(word1)):
for j in range(len(word2)):
if word1[i] == word2[j]:
## row=i+1, col=j+1
dp[i+1][j+1] = dp[i+1-1][j+1-1] + 1
else:
dp[i+1][j+1] = max(dp[i+1-1][j+1], dp[i+1][j+1-1])
lcs_seq = dp[len(word1)][len(word2)]
return(len(word1)-lcs_seq + len(word2)-lcs_seq)
```

MindMap: Two strings become same one => Longest Common Subsequence or Substring.

(Note: these are 2 slightly different problems)

Because I realized deleting character can be arbitrary after failing one of the tests ("park" and "spake"), longest common subsequence is the direction I should follow.