最小编辑距离
最小编辑距离，就是字符串A变成字符串B需要的最少步骤。
其中步骤分为三种：
| 情况 | 说明 | 举例 |
|---|---|---|
| 删除 | A有B没有的 | ‘apple’ 和 ‘pple’ |
| 增加 | A没有B有的 | ‘appe’ 和 ‘apple’ |
| 替换 | AB不一样的 | ‘apple’ 和 ‘appde’ |
- 删除：A有B没有的
- 增加：A没有B有的
- 替换：AB不一样的
比如： - 删除：‘apple’ 和 ‘pple’
- 增加：‘appe’ 和 ‘apple’
- 替换：‘apple’ 和 ‘appde’
每经过以上任一步骤，编辑距离加一。
边界情况：
显然可知，当某一字符串为空时，编辑距离即另一字符串的长度。
如何求最小：
为了获取最小编辑距离，对每一位置考虑以上所有情况。
即考虑替换时的最小，删除时的最小，增加时的最小1
2
3
4
5
6
7
8
9min_dis(strA, strB) =
min(
min_dis(strA[:-1], strB[:-1]) + add， # 替换
min_dis(strA, strB[:-1]) + 1， # 删除
min_dis(strA[:-1], strB) + 1 # 增加
)
其中：
add = 0 当 strA[-1] == strB[-1] 即无需操作
1 当 strA[-1] != strB[-1] 即需要替换操作
完整代码如下：
1 | # python3.5.0+windows+pycharm |