LintCode 编辑距离题目分析代码

题目

给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。

你总共三种操作方法:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

样例 给出 work1="mart" 和 work2="karma"

返回 3

分析

dp[i][j]表示前i个字符到前j个字符的最小操作数 状态转移方程比较简单 当第i个字符与第j个字符相等的时候,自然就是不考虑第i个字符和第j个字符的距离: dp[i][j] = dp[i-1][j-1] 如果他们不相等,那么就有三种情况,

  • 替换一个字符 dp[i][j] = dp[i-1][j]+1
  • 删除一个字符 dp[i][j] = dp[i][j-1]+1
  • 插入一个字符 dp[i][j] = dp[i-1][j-1]+1 然后取三种情况里最小的一个

代码

public class Solution {
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    public int minDistance(String word1, String word2) {
       int n = word1.length();
       int m = word2.length();
       
       int[][] dp = new int[n+1][m+1];
       
       for(int i=0;i<n+1;i++)
           dp[i][0] = i;
       
       for(int i=0;i<m+1;i++)
           dp[0][i] = i;
       
       for(int i=1;i<n+1;i++) {
           for(int j=1;j<m+1;j++) {
               //dp[i][j] = dp[i-1][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-1][j-1], dp[i][j-1]))+1;
           }
       }
       return dp[n][m];
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复...

993
来自专栏haifeiWu与他朋友们的专栏

Python基础(一)

以#开头的语句是注释,解释器会忽略掉注释。其他每一行都是一个语句,当语句以冒号:结尾时,缩进的语句视为代码块。

1575
来自专栏Android干货

Python高级特性:迭代

--------------------------------------------------------------------------------...

831
来自专栏天天

数据类型的转换

1183
来自专栏玄魂工作室

输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字

要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和...

2371
来自专栏WD学习记录

逆波兰表达式

中缀表达式到后缀表达式的转换 要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式,必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求...

1993
来自专栏PHP实战技术

你应该这个姿势学习PHP(2)

2、is_array(),is_bool,is_int(),is_integer(),is_numeric(),is_string(),is_object(),...

4066
来自专栏测试开发架构之路

C++之类和对象的使用(三)

对象数组 如果构造函数只有一个参数,在定义数组时可以直接在等号后面的花括号内提供。Student stud[3]={90,92,01};//合法 如果构造函数...

3419
来自专栏Python小屋

Python内置函数sorted()和列表方法sort()排序规则不得不说的事

Python内置函数sorted()和列表方法sort()可以使用key参数指定排序规则,并且都是稳定排序,也就是说,对于指定规则不能涵盖的元素,本来谁在前面,...

2703
来自专栏小樱的经验随笔

关于int *a[常量]与int (*a)[常量]的分析与区分(详解)

前言: 小伙伴私信我说,int *a[常量]与int (*a)[常量]这个区分不开,C指针,确实是C中最难的部分,也是学C++,JAVA,包括你以后上岗用的非常...

2723

扫码关注云+社区

领取腾讯云代金券