动态规划之字符串编辑距离

February 11, 2018

问题描述 #

给定 2 个字符串 a, b. 编辑距离是将 a 转换为 b 的最少操作次数，操作只允许如下 3 种： 插入一个字符，例如：fj -> fxj 删除一个字符，例如：fxj -> fj 替换一个字符，例如：jyj -> fyj

函数原型：

func LevenshteinDis(str1, str2 string) int {
    ...
}

算法适用场景 #

• 拼写检查
• 输入联想
• 语音识别
• 论文检查
• DNA分析

问题分析 #

假定函数edit_dis(stra, strb)表示，stra到strb的编辑距离。算法问题可以分为四种情况：

1. edit_dis(0, 0) = 0
2. edit_dis(0, strb) = len(strb)
3. edit_dis(stra, strb) = len(stra)
4. edit_dis(stra, strb) = ?

对于4th一般情况，没有办法直接给出求解方式，我们来分析edit_dis(stra+chara, strb+charb)可能的情况：

1. stra能转成strb，那么只需要判断chara是不是等于charb (cur_cost = 0 if chara == charb else 1)
2. stra+chara能转成strb, 那么要让stra + chara 转成strb+ charb, 只需要插入charb就行了
3. 如果stra 可以直接转成strb+charb，那么删除chara就可以转换成功了

综上的分析，可以得到如下DP公式：