区块链技术博客
www.b2bchain.cn

72. 编辑距离 dp[i][j]从word1i位置到word2 j位置最小移动

这篇文章主要介绍了72. 编辑距离 dp[i][j]从word1i位置到word2 j位置最小移动,通过具体代码讲解8077并且分析了72. 编辑距离 dp[i][j]从word1i位置到word2 j位置最小移动的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了72. 编辑距离 dp[i][j]从word1i位置到word2 j位置最小移动。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8077.html。具体如下:

72. 编辑距离 dp[i][j]从word1i位置到word2 j位置最小移动 

 //给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。  // // 你可以对一个单词进行如下三种操作:  // //  // 插入一个字符  // 删除一个字符  // 替换一个字符  //  // //  // // 示例 1:  // // 输入:word1 = "horse", word2 = "ros" //输出:3 //解释: //horse -> rorse (将 'h' 替换为 'r') //rorse -> rose (删除 'r') //rose -> ros (删除 'e') //  // // 示例 2:  // // 输入:word1 = "intention", word2 = "execution" //输出:5 //解释: //intention -> inention (删除 't') //inention -> enention (将 'i' 替换为 'e') //enention -> exention (将 'n' 替换为 'x') //exention -> exection (将 'n' 替换为 'c') //exection -> execution (插入 'u') //  // Related Topics 字符串 动态规划   //leetcode submit region begin(Prohibit modification and deletion) class Solution {     public int minDistance(String word1, String word2) {         int m=word1.length();         int n=word2.length();          int[][] dp=new int[m+1][n+1];         dp[0][0]=0;         //记得加等号 正式字符是从1开始的,0位置为空字符。最多可以到达下标为m或者n的位置         for (int i = 1; i <=m ; i++) {             dp[i][0]=dp[i-1][0]+1;         }         for (int j = 1; j <=n ; j++) {             dp[0][j]=dp[0][j-1]+1;         }         for (int i = 1; i <=m ; i++) {             for (int j = 1; j <=n ; j++) {                 if(word1.charAt(i-1)==word2.charAt(j-1))dp[i][j]=dp[i-1][j-1];                 else dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;             }         }         return dp[m][n];     } } //leetcode submit region end(Prohibit modification and deletion) 

 

本文地址https://www.b2bchain.cn/8077.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 72. 编辑距离 dp[i][j]从word1i位置到word2 j位置最小移动
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们