72. 编辑距离¶
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
| Text Only | |
|---|---|
示例 2:
| Text Only | |
|---|---|
提示:
0 <= word1.length, word2.length <= 500word1和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 新增一项」为什么能合并为一种状态的举例说明:
