算法思想 动态规划。
假设字符下标从1开始。
c[i][j] 表示word1[1~i] 到word2[1~j]的最短编辑距离。
则有递推式:
c[i][j] = min(c[i-1][j],c[i][j-1],c[i-1][j-1])+1; if(i >= 1 && j >= 1 && word[i] != word[j])
c[i-1][j-1]; if(i >= 1 && j >= 1 && word[i] == word[j])
当i == 0|| j ==0时,忽略计算上述中的对应项即可。
说明: c[i][j] = c[i-1][j]+1 表示执行的是删除操作;
c[i][j] = c[i][j-1]+1表示执行的是插入操作;
c[i][j] = c[i-1][j-1] 在word[i]!=word[j] 时表示执行的是替换操作;
代码:
public class Solution { /* c[m+1][n+1]数组 认为word1,word2的下标都是从1开始。因此取具体字符的时候应该注意是i-1,j-1 初始化c[0][0] = 0 */ public int minDistance(String word1, String word2) { // Start typing your Java solution below // DO NOT write main() function if(word1 == null||word1.length() == 0) return word2.length(); if(word2 == null||word2.length() == 0) return word1.length(); int m = word1.length(); int n = word2.length(); int c[][] = new int[m+1][n+1]; c[0][0] = 0; for(int j = 1;j<=n;j++) c[0][j] = j; for(int i = 1;i<=m;i++) c[i][0] = i; for(int i = 1;i<=m;i++) for(int j = 1; j<=n;j++){ int min = c[i-1][j-1]; if(min>c[i][j-1]) min = c[i][j-1]; if(min>c[i-1][j]) min = c[i-1][j]; c[i][j] = min+1; if(word1.charAt(i-1) == word2.charAt(j-1)){ if(c[i][j] > c[i-1][j-1]) c[i][j] = c[i-1][j-1]; } } return c[m][n]; } }
相关推荐
idea leetcode插件 安装方法选择install plugn from disk
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode中文版
vs code LeetCode 插件
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode编辑器leetcode-问题 自定义代码演示 leetcode 编辑器配置 代码文件名: $ ! velocityTool . camelCaseName(${question . titleSlug}) 代码模板: ${question . content} package ...
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
LeetCode 刷题笔记
LeetCode 刷题
(C++)LeetCode刷题题解答案