力扣(LeetCode)72

栏目: 编程工具 · 发布时间: 6年前

内容简介:题目地址:题目描述:

题目地址:

https://leetcode-cn.com/probl...

题目描述:

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

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

1.插入一个字符

2.删除一个字符

3.替换一个字符

解答:

这一题用动态规划,dpi表示word1中0到i的字符所组成的字符串到word2中0到j的字符所组成的字符串的编辑距离。

那么答案则为dpword1.length

那么如何求dpi呢?也就是转移方程。由定义可以知道空字符串变成任意长度字符串的代价为该字符串的长度,也就是说dp0 = j+1,dpi = i+1。这里的i,j最大分别为word1和word2的长度-1。

对于dpi,若word1[i] != word2[j],那么dpi = 1 + min(dpi-1,dpi),这里的解释为删除word1[i]或者删除word2[j],并且比较word1[0-i-1]变成word2[0-j]和word1[0-i]变成word2[0-j-1]的大小,选择小的那个。

若word1[i] == word2[j],那么dpi = min(dpi-1,1 + min(dpi-1,dpi))这里的解释是,增加了一个比较对象,word1[0-i-1]变成word2[0-j-1]。

java ac代码:

class Solution {
    public int minDistance(String word1, String word2) {
        if(word1.length() == 0||word2.length() == 0)return Math.max(word1.length(),word2.length());
        int[][]dp = new int[word1.length()+1][word2.length()+1];
        for(int i = 0;i <= word1.length();i++)
            dp[i][0] = i;
        for(int j = 0;j <= word2.length();j++)
            dp[0][j] = j;
        
        for(int i = 1;i <= word1.length();i++)
            for(int j = 1;j <= word2.length();j++)
            {
                int ans = 1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
                if(word1.charAt(i-1) == word2.charAt(j-1))
                ans = Math.min(ans,dp[i-1][j-1]);
                dp[i][j] = ans;
            }
        return dp[word1.length()][word2.length()];
    }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

企业应用架构模式

企业应用架构模式

Martin Fowler / 王怀民、周斌 / 机械工业出版社 / 2010-4 / 59.00元

《企业应用架构模式》作者是当今面向对象软件开发的权威,他在一组专家级合作者的帮助下,将40多种经常出现的解决方案转化成模式,最终写成这本能够应用于任何一种企业应用平台的、关于解决方案的、不可或缺的手册。《企业应用架构模式》获得了2003年度美国软件开发杂志图书类的生产效率奖和读者选择奖。《企业应用架构模式》分为两大部分。第一部分是关于如何开发企业应用的简单介绍。第二部分是《企业应用架构模式》的主体......一起来看看 《企业应用架构模式》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码