72. 编辑距离¶
给你两个单词 word1
和 word2
, 请返回将 word1
转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
Text Only | |
---|---|
示例 2:
Text Only | |
---|---|
提示:
0 <= word1.length, word2.length <= 500
word1
和word2
由小写英文字母组成
个人题解¶
动态规划¶
dp[i][j]
为区间分别为[0, i - 1]
,[0, j - 1]
的word1
和word2
子串,要使得其相等,最少需要操作(增/删/改)的次数;dp
初始化:当word2/1
为空时,word1/2
显然要删除i/j
个字母,才能使得其相等;- 状态转移:见下方推导说明。
状态转移¶
题目允许三种操作方式,分别为增/删/改,根据三种操作方式,可以分析出以下情况:
-
当
word1[i - 1] == word2[j - 1]
时,显然不用做任何操作,直接获取当前字母之前部分的状态:dp[i][j] = dp[i - 1][j - 1]
; -
当
word1[i - 1] != word2[j - 1]
时,分别做三种操作:- 对
word1
当前项进行删除/对word2
新增一项,转移为区间[0, i - 2]
,[0, j - 1]
的word1
和word2
子串的状态,所以从[i - 1][j]
获取状态:dp[i][j] = dp[i - 1][j] + 1
; - 对
word2
当前项进行删除/对word1
新增一项,转移为区间[0, i - 1]
,[0, j - 2]
的word1
和word2
子串的状态,所以从[i][j - 1]
获取状态:dp[i][j] = dp[i][j - 1] + 1
; - 对
word1/2
当前项进行修改(以修改word1
为例),将word1[i - 1] = word2[j - 1]
,显然,二者的长度没有发生改变,所以从[i - 1][j - 1]
获取状态:dp[i][j] = dp[i - 1][j - 1] + 1
。
综上:
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1
。 - 对
关于 「word1/2
删除当前项/ word2/1
新增一项」为什么能合并为一种状态的举例说明: