LeetCode 072 Edit Distance

LeetCode

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three 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’)

Constraints: 0 <= word1.length, word2.length <= 500
* word1 and word2 consist of lowercase English letters.

题目大意：

求编辑两个字符串的最短距离。编辑操作含加删一个字符，替换一个字符。

解题思路：

求最值且涉及到字符串考虑用DP。递归式为

dp[i][j] = dp[i-1][j-1]                                   if word1[i-1] == word[j-1]  
         = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, otherwise

解题步骤：

N/A

注意事项：

1. 初始值先word2长度再word1.
2. 初始化上和左边界，表示当一个字符串为空时，另一个字符串的编辑距离是其长度。

Python代码：

# dp[i][j] = dp[i-1][j-1] if word1[i-1] == word[j-1]
#          = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, otherwise
def minDistance(self, word1: str, word2: str) -> int:
	dp = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]
	for i in range(1, len(dp)):
		dp[i][0] = i
	for j in range(1, len(dp[0])):
		dp[0][j] = j
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if word1[i - 1] == word2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
	return dp[-1][-1]

算法分析：

时间复杂度为O(nm)，空间复杂度O(nm)