最小编辑距离
编辑 最小 距离
2023-06-13 09:16:11 时间
问题描述
给定 2 个字符串 a, b. 编辑距离是将 a 转换为 b 的最少操作次数,操作只允许如下 3 种:
- 插入一个字符,例如:fj -> fxj
- 删除一个字符,例如:fxj -> fj
- 替换一个字符,例如:jxj -> fyj
思路
用分治的思想解决比较简单,将复杂的问题分解成相似的子问题
- 假设字符串 a, 共 m 位,从 a[1] 到 a[m]
- 字符串 b, 共 m 位,从 b[1] 到 b[n]
- d[i][j] 表示字符串 a[1]-a[i] 转换为 b[1]-b[i] 的编辑距离
那么有如下递归规律( a[i] 和 b[j] 分别是字符串 a 和 b 的最后一位):
- 当 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
递归边界:
- a[i][0] = i , b 字符串为空,表示将 a[1]-a[i] 全部删除,所以编辑距离为 i
- a[0][j] = j , a 字符串为空,表示 a 插入 b[1]-b[j] ,所以编辑距离为 j
代码
按照上面的思路将代码写下来
int edit_distance(char *a, char *b, int i, int j)
{
if (j == 0) {
return i;
} else if (i == 0) {
return j;
// 算法中 a, b 字符串下标从 1 开始,c 语言从 0 开始,所以 -1
} else if (a[i-1] == b[j-1]) {
return edit_distance(a, b, i - 1, j - 1);
} else {
return min_of_three(edit_distance(a, b, i - 1, j) + 1,
edit_distance(a, b, i, j - 1) + 1,
edit_distance(a, b, i - 1, j - 1) + 1);
}
}
edit_distance(stra, strb, strlen(stra), strlen(strb));
但是有个严重的问题,就是代码的性能很低下,时间复杂度是指数增长的
上面的代码中,很多相同的子问题其实是经过了多次求解,解决这类问题的办法是用动态规划思想优化时间复杂度
像以上解决思路,是从后往前算的,比如我想知道 edit_distance(a, b, i, j) 我可能需要知道 edit_distance(a, b, i-1, j-1) ,有一种想法不错,就是从前往后算,先算出各个子问题,然后根据子问题,计算出原问题, 对于这个问题性能不错,而且也挺容易理解,下面就来说一说 例如以字符串 a = “fxy”, b = “fab” 为例
- 首先建立一个矩阵,用来存放子问题及原问题的编辑距离,并将递归边界在矩阵中填好,如下:
- 然后计算 i = 1, j = 1 所对应的编辑距离:比较 a[i] 和 b[j] 是否相等然后根据递归规律算出这个值 比如在这种情况下 a[i] = f 和 b[j] = f , 那么 d[i][j] 就等于 d[i-1][j-1] 等于 0,然后计算 i = 1, j = 2 直到算出 i = 3, j = 3, 原问题的编辑距离就等于 d[3][3] ,最终矩阵如下:
现在的时间复杂度已到了可接受范围,为 O(mn)
代码如下:
function minDistance(s1, s2) {
const len1 = s1.length
const len2 = s2.length
let matrix = []
for (let i = 0; i <= len1; i++) {
// 构造二维数组
matrix[i] = new Array()
for (let j = 0; j <= len2; j++) {
// 初始化
if (i == 0) {
matrix[i][j] = j
} else if (j == 0) {
matrix[i][j] = i
} else {
// 进行最小值分析
let cost = 0
if (s1[i - 1] != s2[j - 1]) { // 相同为0,不同置1
cost = 1
}
const temp = matrix[i - 1][j - 1] + cost
matrix[i][j] = Math.min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, temp)
}
}
}
return matrix[len1][len2] //返回右下角的值
}
minDistance('jary','jerry') // 2
相关文章
- AngularJS进阶(十一)AngularJS实现表格数据的编辑,更新和删除[通俗易懂]
- Filmage Screen for Mac(屏幕录制和视频编辑软件)
- 会声会影视频编辑软件2023最新完整版下载教程
- Artstudio Pro for mac 5.1.7 不错的绘画和照片编辑应用
- Linux命令掌握:编辑文件.(编辑文件linux命令)
- Linux下调节命令:掌握超级能力(linux下编辑命令)
- 器学习Linux:掌握vim编辑器的秘密(linuxvim编辑)
- 行Linux输入命令行编辑指南(linux进入编辑命令)
- MSSQL 语句编辑技巧 – 提高开发效率(mssql 语句编辑)
- Linux环境下Web开发的HTML文件编辑(html文件 Linux)
- textarea支持图形编辑的实现方法
- javascript双击文本框编辑功能代码
- 利用jQuery实现可以编辑的表格