dp:最短编辑距离

秒速五厘米 2021-11-08 18:04 315阅读 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 条评论，315人围观）

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

相关阅读

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

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

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

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

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

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

相关 Codeforces Round #739 (Div. 3)（编辑距离+数位dp）

a int n; int arr[N]; void solve() { cin >> n; cout <

本是古典何须时尚/ 2022年09月06日 00:21/ 0 赞/ 125 阅读

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

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

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

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

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

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

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

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

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

相关编辑距离

编辑距离算法算法过程 1. str1或str2的长度为0返回另一个字符串的长度。 if(str1.length==0) return str2.leng

比眉伴天荒/ 2022年06月11日 04:24/ 0 赞/ 221 阅读

相关编辑距离

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

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

相关 leetcode 72. Edit Distance DP动态规划 + 编辑距离

Given two words word1 and word2, find the minimum number of steps required to convert wo

妖狐艹你老母/ 2022年06月08日 01:24/ 0 赞/ 243 阅读

相关 dp:最短编辑距离

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

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