最小编辑距离

蔚落 2022-10-29 11:20 18阅读 0赞

/** * 求两个字符串的最小编辑距离 * dp[i][j]表示s1[0...i-1]和s[0...j-1]的最小编辑距离 */
    public class Solution9 { 
        public static void main(String[] args) { 
            String s1 = "intention";
            String s2 = "execution";
            System.out.println(minDistance(s1, s2));
        }
    
        static int minDistance(String s1, String s2) { 
            int[][] dp = new int[s1.length()+1][s2.length()+1];
            for (int i = 0; i <= s1.length(); i++) { 
                dp[i][0] = i;
            }
            for (int j = 0; j <= s2.length(); j++) { 
                dp[0][j]= j;
            }
            for (int i = 1; i <= s1.length(); i++) { 
                for (int j = 1; j <= s2.length(); j++) { 
                    // 如果对应字符相等，那么取上一步的结果+1
                    if (s1.charAt(i-1) == s2.charAt(j-1)) { 
                        dp[i][j] = dp[i-1][j-1];
                    } else { 
                        // 插入，删除，替换
                        dp[i][j] = Math.min(dp[i-1][j] + 1, Math.min(dp[i][j-1] + 1, dp[i-1][j-1] + 1));
                    }
                }
            }
            return dp[s1.length()][s2.length()];
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Java版本最小编辑距离

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

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

相关求字符串的最小编辑距离动态规划（java实现）

目录题目算法思路实现代码 -------------------- 题目 Levenshtein 距离，又称[编辑距离][Link 1]，指的是两个字符串

妖狐艹你老母/ 2023年09月27日 17:28/ 0 赞/ 112 阅读

相关最小编辑距离

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

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

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

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

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

相关 72. 编辑距离

> 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。 > > 你可以对一个单词进行如下三种操作： > > 插入

拼搏现实的明天。/ 2022年10月10日 01:51/ 0 赞/ 179 阅读

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

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

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

相关编辑距离

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

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

相关编辑距离

一、问题描述设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 阅读

相关 React-虚拟dom-diff算法，Levenshtein Distance最小编辑距离

Levenshtein Distance是最小编辑距离的一种实现，网上搜到的一些python的实现，现在用前端的JavaScript来实现一下。什么是最小编辑距离？请看[斯坦福

太过爱你忘了你带给我的痛/ 2021年06月10日 20:40/ 0 赞/ 454 阅读