原题
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:
a) Insert a character
b) Delete a character
c) Replace a character
意思是
给两个单词，求从单词1变换到单词2的最小步数，变换的操作有 增加字符，删除字符和替换字符三种。
比如从”apaed” 到 “dapade” 需要3步。
分析
这道题实际上是一个动态规划题，我们用d(i,j)表示第一个单词的i个字符变换到第二个单词j个字符的步骤，显然d(i,0)=i,d(0,j)=j,都只需要依次删除相应的字符。
那么d(i+1,j+1)有几种可能性呢？
- 首先从d(i+1,j)到d(i+1,j+1)只是第二个单词增加了一个字符，即d(i+1,j+1)=d(i+1,j)+1
- 从d(i,j+1)到d(i+1,j+1)是第一个单词多了一个字符，那么只需要增加在d(i,j+1)的基础上删除一个字符的步骤，即d(i+1,j+1)=d(i,j+1)+1
- 从d(i,j)到d(i+1,j+1)，如果第一个单词的第i+1个字符和第二个单词的j+1个字符相等，则d(i+1,j+1)=d(i,1)，若不相等，则需要在d(i,j)的基础上把第i+1个字符替换为j+1个字符。即d(i+1,j+1)=d(i,j)+1
以上三种情况都有可能，最终d(i+1,j+1)取三种情况的最小值
举个栗子：
从字符串”dabca”变换到”bcddc”.
我们写出d(i,j)矩阵
| d | a | b | c | a | ||
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | |
| b | 1 | 1 | 2 | 2 | 3 | 4 |
| c | 2 | 2 | 2 | 3 | 2 | 3 |
| d | 3 | 2 | 3 | 3 | 3 | 3 |
| d | 4 | 3 | 3 | 4 | 4 | 4 |
| c | 5 | 4 | 4 | 4 | 4 | 5 |
最终答案为5
代码
python代码如下
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
len1,len2 = len(word1),len(word2)
if len1 == 0 or len2 == 0:
return max(len1, len2)
dist = [[0 for i in range(len2+1)] for j in range(len1+1)]
for i in range(len1+1):
dist[i][0] = i
for j in range(len2+1):
dist[0][j] = j
for i in range(len1):
for j in range(len2):
if word1[i] == word2[j]:
dist[i+1][j+1]=dist[i][j]
else:
dist[i+1][j+1]=min(dist[i][j],dist[i][j+1],dist[i+1][j])+1
return dist[len1][len2]