最小编辑距离问题:递归与动态规划 #106
最小编辑距离问题:递归与动态规划 #106
Open
youngwind opened this issue on 14 Jun 2017 · 13 comments
Comments
Assignees
No one assigned
Labels
Projects
None yet
Milestone
No milestone
8 participants
Owner
youngwind commented on 14 Jun 2017 •
edited
继上一篇 #104 ,本来是在研究虚拟 DOM 算法的,看到了 livoras 的这篇文章,觉得写得很好!珠玉在前,我便不再赘述了。该文章中提到:列表更新本质上是一个最小编辑距离问题,不过并未就此详细展开。今天,我们来具体看看这个问题。 问题给定两个字符串 a 和 b,只允许以下三种操作:
求:把 a 转换成 b 的最小操作次数,也就是所谓的最小编辑距离。 求解这个问题,一般有两种思路:递归和动态规划。 递归所谓递归,便是把大问题”分治“成类似的小问题。
代码实现 /** * 递归算法 * @param {string} a * @param {string} b * @param {number} i 字符串 a 的长度 * @param {number} j 字符串 b 的长度 * @returns {number} 从 a → b 的最小编辑距离 */ function recursion(a, b, i, j) { if (j === 0) { return i; } else if (i === 0) { return j; } else if (a[i - 1] === b [j - 1]) { return recursion(a, b, i - 1, j - 1); } else { let m1 = recursion(a, b, i - 1, j) + 1; let m2 = recursion(a, b, i, j - 1) + 1; let m3 = recursion(a, b, i - 1, j - 1) + 1; return Math.min(m1, m2, m3); } } 动态规划动态规划看起来跟递归很像,不过推理逻辑正好是反过来的。递归的逻辑是:“要求得 d[m][n],先要求得 d[m-1][n-1]……”,动态规划的逻辑是:“先求得 d[m-1][n-1],再求 d[m][n]……”这是它们的主要区别。
接着用同样的方式,可以求得 d[1][2]、d[1][3]、……、d[1][n],然后继续求得 d[2][1]、d[2][2]、……、d[2][n],一直到 d[m][n]。代码实现如下: /** * 动态规划算法 * @param {string} a * @param {string} b * @returns {number} 从 a → b 的最小编辑距离 */ function dynamicPlanning(a, b) { let lenA = a.length; let lenB = b.length; let d = []; d[0] = []; for (let j = 0; j <= lenB; j++) { d[0].push(j); } for (let i = 0; i <= lenA; i++) { if (d[i]) { d[i][0] = i; } else { d[i] = []; d[i][0] = i; } } for (let i = 1; i <= lenA; i++) { for (let j = 1; j <= lenB; j++) { if (a[i - 1] === b[j - 1]) { d[i][j] = d[i - 1][j - 1]; } else { let m1 = d[i - 1][j] + 1; let m2 = d[i][j - 1] + 1; let m3 = d[i - 1][j - 1] + 1; d[i][j] = Math.min(m1, m2, m3); } } } return d[lenA][lenB]; } 对比与实证这两种算法哪一个更快呢? 参考资料 |