Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Solution
- dp[i][j]: 把单词word1[1:i] 转成 word21:j所用步数
if word[i+1] == word[j+1]
dp[i+1][j+1] = Min(dp[i][j+1]+1, dp[i+1][j]+1, dp[i][j] + 0]
else
dp[i+1][j+1] = Min(dp[i][j+1]+1, dp[i+1][j]+1, dp[i][j] + 1]
(Edit-Distance.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
if word1 == None and word2 == None:
return 0
elif word1 == None:
return len(word2)
elif word2 == None:
return len(word1)
l1 = len(word1)
l2 = len(word2)
dp = [[0]*(l1+1) for x in range(l2+1)]
# 初始化dp
for i in range(l2+1):
dp[i][0] = i
for i in range(l1+1):
dp[0][i] = i
for i in range(1,l2+1):
for j in range(1,l1+1):
dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1
if word1[j-1] == word2[i-1]:
dp[i][j] = min(dp[i][j], dp[i-1][j-1])
else:
dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1)
return dp[l2][l1]
|