最小编辑距离,除了DP有没有其他套路?

增删改距离都为1,求最小距离的。 abcd abed 编辑距离为1。 这个题目还有别的思路吗。
全部评论
递归吧 从上往下 const m = word1.length; const n = word2.length; const memo = new Array(m).fill(0).map(() => new Array(n).fill(-1)) const dfs = (i, j) => { if(i < 0) return j + 1; if(j < 0) return i + 1; if(memo[i][j] !== -1) return memo[i][j] if(word1[i] === word2[j]) return memo[i][j] = dfs(i - 1, j - 1); return memo[i][j] = Math.min(dfs(i - 1, j - 1), dfs(i -1, j), dfs(i, j -1)) + 1 } dfs(m - 1, n - 1); return memo[m - 1][n - 1]
点赞 回复 分享
发布于 12-10 11:50 北京
求问如果此题加上swap操作应该怎么做?
点赞 回复 分享
发布于 2016-09-22 02:37
动态规划可做
点赞 回复 分享
发布于 2016-09-22 00:57
广搜吧
点赞 回复 分享
发布于 2016-09-21 23:43

相关推荐

不愿透露姓名的神秘牛友
11-21 11:29
已编辑
斯卡蒂味的鱼汤:知道你不会来数马,就不捞你😂最近数马疯狂扩招,招聘要求挺低的,你能力肯定够,应该就是因为太强了,知道你不会来才不捞你
投递腾讯云智研发等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务