LeetCode 72. Edit Distance
Description
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros" Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution" Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
描述
给定两个单词word1和word2，找到将word1转换为word2所需的最小操作数。
您对单词允许以下3个操作：
插入一个字符
删除一个字符
替换一个字符
思路
- 题意是给定两个单词，问将单词1变成单词二最少需要几次操作.允许的操作是:替换一个字符，增加一个字符，删除一个字符.类似数据库的增删改.
- 此题目考察动态规划.
- 我们维护一个二维数组Matrixp[row][col],如上图.接下来以字符串C1[3]和C2[2]为例说明(以下数组下标从1开始).
- 我们有三种方法把C1[1:3]变成C2[1:2]
1.如果我们已经知道C1[1:3]变成C2[1:1]的步数Step1,我们删除C1的最后一个元素.
2.如果我们已经知道C1[1:2]变成C2[1:2]的步数Step2,我们为C1增加一个元素.
3.如果我们已经知道C1[1:2]变成C2[1:1]的步数Step3,我们改变C1[3]为C2[2](如果元素已经相等，则不需要改变).
- 把C1[3]变成C2[2]为step1，step2，step3中的最小值,我们有递推关系式.
- 同理我们把C1[1:3]变成C2[1:1]也有如上的三步.
import sys
from pprint import pprint
class Solution:
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
# 获取字符串word1和字符串word2的长度
numword1, numword2 = len(word1), len(word2)
# 如果字符串word1长度为0，则字符串1变成字符串2需要numword2步
if numword1 == 0:
return numword2
# 如果字符串2长度为0，则字符串1变成字符串0需要numword1步
if numword2 == 0:
return numword1
# 声明结果数组
res = []
# 初始化二维矩阵，每一个位置都初始化为Int类型的最大值
for _ in range(numword1+1):
res.append([sys.maxsize for _ in range(numword2+1)])
# 初始化矩阵第一行，表示一个空字符变成当前长度的字符需要几步
for row in range(numword1+1):
res[row][0] = row
# 初始化矩阵第一列，表示一个空字符变成当前字符需要几步
for col in range(numword2+1):
res[0][col] = col
# 遍历二维数组的每一个位置
for row in range(1, numword1+1):
for col in range(1, numword2+1):
# 如果两个字符串当前字符相等
if word1[row-1] == word2[col-1]:
res[row][col] = min(res[row][col-1]+1,
res[row-1][col-1], res[row-1][col]+1)
# 如果两个字符当前字符不相等
else:
res[row][col] = min(res[row][col-1]+1,
res[row-1][col-1]+1, res[row-1][col]+1)
# 返回最后一个位置的值
return res[numword1][numword2]
if __name__ == "__main__":
so = Solution()
res = so.minDistance("intention", "execution")
pprint(res)
