编辑距离
编辑距离
给你两个单词 word1
和 word2
, 请返回将 word1
转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
1 | 输入:word1 = "horse", word2 = "ros" |
示例 2:
1 | 输入:word1 = "intention", word2 = "execution" |
提示:
0 <= word1.length, word2.length <= 500
word1
和word2
由小写英文字母组成
f[i][j]
表示从[0,i-1]
转换成[0,j-1]
的最少操作次数。
考虑word1.charAt(i-1)
和word2.charAt(j-1)
的大小关系,
- 如果
word1.charAt(i-1)==word2.charAt(j-1)
,word1不需要做任何修改直接从上一个状态转移f[i][j]=f[i-1][j-1]
- 如果
word1.charAt(i-1)!=word2.charAt(j-1)
,word1
可以通过三种方式变为和word2
相等。- 插入。如果在
word1
后插入一个字母能变成word2
,说明word1
中前i
个字母等于word2
中前j-1
个字母,状态转移方程为f[i][j]=f[i][j-1]+1
- 删除。如果在
word1
后删除一个字母能变成word2
,说明word1
中前i-1
个字母等于word2
中前j
个字母,状态转移方程为f[i][j]=f[i-1][j]+1
- 修改。如果在
word1
后修改一个字母能变成word2
,说明word1
中前i-1
个字母等于word2
中前j-1
个字母,状态转移方程为f[i][j]=f[i-1][j-1]+1
- 插入。如果在
- 对上述三种情况求最小值
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 面试资料!