题目
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
分析
以horse转换成ros为例, 很多题解会使用下面这个表格
| ‘’ | r | o | s | 行号 | |
|---|---|---|---|---|---|
| ‘’ | 0 | 1 | 2 | 3 | 1 |
| h | 1 | 1 | 2 | 3 | 2 |
| o | 2 | 2 | 1 | 2 | 3 |
| r | 3 | 2 | 2 | 2 | 4 |
| s | 4 | 3 | 3 | 2 | 5 |
| e | 5 | 4 | 4 | 3 | 6 |
| 列号 | 1 | 2 | 3 | 4 | - |
这个表格的含义如下:
第一行第一列, 表示空字符串到空字符串的编辑距离是0
第一行第二列, 表示空字符串到r的编辑距离为1
第一行第二列, 表示空字符串到ro的编辑距离为2
以此类推
最终结果就是右下角单元格的值
每个单元格的取值计算逻辑是考虑该单元格左/上/左上的单元格的值
如果当前单元格对应的word1和word2字符相同, 则
f(当前单元格)=min(f(左)+1, f(上)+1, f(左上))
否则
f(当前单元格)=min(f(左)+1, f(上)+1, f(左上)+1)
其中如果从左边单元格到达当前单元格, 代表一个插入操作
如果从上边单元格到达当前单元格, 代表一个删除操作
如果从左上单元格到达当前单元格, 代表替换或者无操作(如果刚好字符相同)
然而如何证明这个算法是完备的? 即它考虑了所有可能的情况并得到了最优结果?
考虑horse -> ros的情况
对于ros的最后一个字符s, 它出现在这个位置可能是因为下面几种情况
- 本来就在这里
- 把本来在这里的字符替换成s
- 在末尾插入一个字符s
- 它不动, 删除后面的字符
其中1 和 2对应从单元格左上到达的两种情况
3对应从左边单元格到达的情况
4对应从上面单元格到达的情况
因此前述的推理已经覆盖了所有情况, 所得到的就是最优解