dp:最短编辑距离

秒速五厘米 2021-11-08 18:04 332阅读 0赞

最短编辑距离问题：详细解释（[https://blog.csdn.net/ac540101928/article/details/52786435][https_blog.csdn.net_ac540101928_article_details_52786435]）

package bytedance.bytedance;
    
    import java.util.Scanner;
    
    //将字符串变为奇数偶数之间不同的最短编辑距离
    //变形：字符串A到B的最短编辑距离
    //输入fxpimu、xwrs，输出5，输入cafe和coffee。输出3
    public class MinEditLength {
        public static void main(String[] args) {
            Scanner in=new Scanner(System.in);
            String a=in.nextLine();
            String b=in.nextLine();
            System.out.println(test(a,b));
        }
        public static int test(String a,String b){
            if (a.equals(null)||b.equals(null))
                return 0;
            if (a==b){
                return 0;
            }
            int result=0;
            int[][] dp=new int[a.length()+1][b.length()+1];
            //初始化
            for (int i = 0; i <dp.length ; i++) {
                dp[i][0]=i;
            } for (int i = 0; i <dp[0].length ; i++) {
                dp[0][i]=i;
            }
            for (int i = 1; i <dp.length ; i++) {
                for (int j = 1; j <dp[0].length ; j++) {
                int temp=Math.min(dp[i][j-1]+1,dp[i-1][j]+1);
                dp[i][j]=Math.min(temp,dp[i-1][j-1]+((a.charAt(i-1)==b.charAt(j-1))?0:1));
                result=dp[i][j];
                }
            }
            return result;
        }
    }

[https_blog.csdn.net_ac540101928_article_details_52786435]: https://blog.csdn.net/ac540101928/article/details/52786435

发表评论取消回复

表情：

评论列表（有 0 条评论，332人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java版本最小编辑距离

基于上诉的需求，其中一种解决方案就是使用。

迷南。/ 2024年04月17日 06:14/ 0 赞/ 81 阅读

相关 51nod 1183 编辑距离 dp

[1183 编辑距离][1183] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [1183]: http://www.51no

阳光穿透心脏的1/2处/ 2024年02月17日 20:35/ 0 赞/ 53 阅读

相关线性DP AcWing 899. 编辑距离

线性DP AcWing 899. 编辑距离原题链接 [AcWing 899. 编辑距离][AcWing 899.] 算法标签动态规划线性DP 代码

向右看齐/ 2023年09月28日 13:01/ 0 赞/ 110 阅读

相关最小编辑距离

/ 求两个字符串的最小编辑距离 dp[i][j]表示s1[0...i-1]和s[0...j-1]的最小编辑距离 / public class Solutio

蔚落/ 2022年10月29日 11:20/ 0 赞/ 18 阅读

相关最小编辑代价（编辑距离问题改进版）

题目描述给定两个字符串str1和str2，再给定三个整数ic，dc，rc，分别代表插入、删除、替换一个字符的代价，返回将str1编辑成str2的最小代价。该题是基于

谁借莪１个温暖的怀抱￠/ 2022年10月16日 09:45/ 0 赞/ 172 阅读

相关 51nod 1183编辑距离经典dp

编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个

秒速五厘米/ 2022年08月20日 12:22/ 0 赞/ 161 阅读

相关 AGTC(动态规划-最短编辑距离)

AGTC <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

╰半橙微兮°/ 2022年08月02日 14:49/ 0 赞/ 234 阅读

相关字符串的修改（动态规划-最短编辑距离）

1187: 字符串的修改 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 6 Solved: 5 \[ [S

比眉伴天荒/ 2022年08月02日 14:49/ 0 赞/ 197 阅读

相关编辑距离

一、问题描述设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：（1）删除一个字符；（2）插入一个字符；（3）

逃离我推掉我的手/ 2022年06月10日 09:08/ 0 赞/ 273 阅读

相关 dp:最短编辑距离

最短编辑距离问题：详细解释（[https://blog.csdn.net/ac540101928/article/details/52786435][https_blog.cs

秒速五厘米/ 2021年11月08日 18:04/ 0 赞/ 333 阅读