首页 > 其他 > 详细

[转载]动态规划解决字符串编辑距离问题

时间:2019-10-12 22:02:08      阅读:134      评论:0      收藏:0      [点我收藏+]

[转载]动态规划解决字符串编辑距离问题

本文大部分内容转载自:https://www.dreamxu.com/books/dsa/dp/edit-distance.html

问题描述

给定 2 个字符串 a, b. 编辑距离是将 a 转换为 b 的最少操作次数,操作只允许如下 3 种:

  1. 插入一个字符,例如:fj -> fxj
  2. 删除一个字符,例如:fxj -> fj
  3. 替换一个字符,例如:jxj -> fyj

解决思路

假设字符串 a, 共 m 位,从 a[1]a[m]
字符串 b, 共 n 位,从 b[1]b[n]
d[i][j] 表示字符串 a[1]-a[i] 转换为 b[1]-b[j] 的编辑距离

那么有如下递归规律(a[i]b[j] 分别是字符串 a 和 b 的最后一位):

  1. a[i] 等于 b[j] 时,d[i][j] = d[i-1][j-1], 比如 fxy -> fay 的编辑距离等于 fx -> fa 的编辑距离

a[i]不等于b[j]时,d[i][j]等于如下 3 项的最小值:

  • d[i-1][j] + 1(删除 a[i]), 比如 fxy -> fab 的编辑距离 = fx -> fab 的编辑距离 + 1
  • d[i][j-1] + 1(插入 b[j]), 比如 fxy -> fab 的编辑距离 = fxyb -> fab 的编辑距离 + 1 = fxy -> fa 的编辑距离 + 1
  • d[i-1][j-1] + 1(将 a[i] 替换为 b[j]), 比如 fxy -> fab 的编辑距离 = fxb -> fab 的编辑距离 + 1 = fx -> fa 的编辑距离 + 1

递归边界:

  1. a[i][0] = i, b 字符串为空,表示将 a[1]-a[i] 全部删除,所以编辑距离为 i
  2. a[0][j] = j, a 字符串为空,表示 a 插入 b[1]-b[j],所以编辑距离为 j

剩下的就没啥了,做表就完事了,关键是上面提到的那个思路。

注意,虽然上面写的例子都是字符串a转换成字符串b的距离,但是这个其实是符合交换律的,例如:

a转换为b需要依次经过 在末尾添加字符x->修改第k位由q变成w->删除第z位的字符Az

那么B变成a就是: 在第z位加上Az->修改第k位由w变成q->删除末尾的x

由此可见,编辑距离是符合交换律的。

时间复杂度和空间复杂度分析

就是顺带一提,因为使用动态规划要制表,所以必然是O(mn),m和n分别是两个字符串的长度,空间复杂度也是这个

[转载]动态规划解决字符串编辑距离问题

原文:https://www.cnblogs.com/jiading/p/11664026.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!