leetcode72-编辑距离

原题

给你两个单词 word1word2 ,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

 
示例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')

解法

思想

编辑距离算法,和KMP算法一样,属于字符串处理里面的经典算法了,KMP算法属于精准模式匹配,而编辑距离算法用于处理两个字符串之间的相似度,也属于一种匹配方式。

一般来说,编辑距离越小,两个字符串的相似度越大。 并且编辑距离算法广泛运用于生产中,例如搜索引擎通过编辑距离算法来智能识错,word软件通过编辑距离算法做拼写检查。

思想就是动态规划:

leetcode72-编辑距离

画一个矩阵,中间的格子代表从一个字符串到另一个字符串的编辑距离。

对于第一行、第一列,我们提前赋值1~n,代表仅通过插入的方式计算的编辑距离。

然后,对于任意一个格子,例如图中的红色格子dp[m][n],它可能由字符串A插入一个字符、字符串B插入一个字符,字符串A修改一个字符得到,对于修改字符,如果两个字符串在该位置上的字符相同,则不用修改,对应的最小编辑距离就是min(dp[m][n-1],dp[m-1][n],dp[m-1][n-1]-1)+1,实际上最小的必是dp[m-1][n-1]-1,即此时编辑距离为dp[m-1][n-1],如果两个字符串在该位置上的字符不同,则需要修改最后一个字符,此时最小编辑距离为min(dp[m][n-1],dp[m-1][n],dp[m-1][n-1])+1

代码

class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // 第一行
        for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
        // 第一列
        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
        return dp[n1][n2];  
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode72-%e7%bc%96%e8%be%91%e8%b7%9d%e7%a6%bb/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月5日
下一篇 2020年4月6日

相关推荐

  • leetcode21-合并两个有序链表

    原题 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入: 1->2->4, 1->3->4 输出: 1->1->2->3-…

    2019年12月17日
    0100
  • 程序员面试金典17.16-按摩师

    原题(来源Leetcode) 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,…

    算法 2020年3月24日
    0930
  • leetcode611-有效三角形的个数

    原题 给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用…

    2020年2月8日
    070
  • leetcode429-N叉树的层序遍历

    原题 给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:…

    2020年1月20日
    0140
  • leetcode162-寻找峰值

    原题 峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。 数组可能包含多个峰值,在这种情况…

    算法 2020年1月3日
    060
  • leetcode289-生命游戏

    原题 根据 百度百科 ,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞…

    算法 2020年4月2日
    0300
  • leetcode71-简化路径

    原题 以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。 在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..…

    算法 2020年1月23日
    090
  • leetcode445-两数相加II

    原题 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外,这两个数字都…

    算法 2020年4月14日
    0290
  • leetcode331-验证二叉树的前序序列化

    原题 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。 _9_ / \ 3 2…

    算法 2020年1月26日
    090
  • leetcode221-最大正方形

    原题 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 …

    算法 2020年5月8日
    0110

发表回复

登录后才能评论