编辑距离问题（JAVA版）

小鱼儿 2023-06-08 06:16 15阅读 0赞

最近好久不写博客了，一直被动态规划狂虐

设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括(1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。  
例：fxpims  xwrs

结果：4

代码如下：

public static int editDistant2(String a, String b) {
    		if (a == null || b == null) {
    			return -1;
    		}
    		int c[][] = new int[a.length()][b.length()];
    		for (int i = 0; i < a.length(); i++) {
    			for (int j = 0; j < b.length(); j++) {
    				//初始化01234567
    				if (i == 0) {
    					c[i][j] = j;
    				} else if (j == 0) {
    					c[i][j] = i;
    				//如果相等的话
    				}else if(a.charAt(i)==b.charAt(j)) {
    					c[i][j]=c[i-1][j-1];
    				}else {
    					c[i][j]=Math.min(c[i][j-1], Math.min(c[i-1][j], c[i-1][j-1]))+1;
    				}
    			}
    		}
    		for(int i=0;i<a.length();i++) {
    			for(int j=0;j<b.length();j++) {
    				System.out.print("  " + c[i][j]);
    			}
    			System.out.println();
    		}
    		return c[a.length()-1][b.length()-1];
    	}

思路如下表

x  w  r  s
      f 0  1  2  3
      x 1  1  2  3
      p 2  2  2  3
      i 3  3  3  3
      m 4  4  4  4
      s 5  5  5  4

发表评论取消回复

表情：

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

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

相关阅读

相关【Java版oj】day22微信红包、编辑距离

目录一、微信红包（1）原题再现（2）问题分析（3）完整代码二、编辑距离（1）原题再现（2）问题分析（3）完整代码 ------------

约定不等于承诺〃/ 2024年03月24日 13:22/ 0 赞/ 29 阅读

相关编辑距离问题（JAVA版）

最近好久不写博客了，一直被动态规划狂虐设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括(1)删除一个字符； (2)插入一个字符； (

小鱼儿/ 2023年06月08日 06:16/ 0 赞/ 16 阅读

相关算法--编辑距离问题

![在这里插入图片描述][20201113164317331.png_pic_center] 该动态规划方程借鉴博客 [https://www.cnblogs.com/

电玩女神/ 2022年12月21日 02:25/ 0 赞/ 175 阅读

相关理解编辑距离

顾名思义，编辑距离（Edit distance）是一种距离，用于衡量两个字符串之间的远近程度，方式是一个字符串至少需要多少次基础变换才能变成另一个字符串，可应用在拼写检查、判断

朴灿烈づ我的快乐病毒、/ 2022年12月17日 13:56/ 0 赞/ 227 阅读

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

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

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

相关 72. 编辑距离

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

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

相关编辑距离

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

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

相关编辑距离

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

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

相关详解编辑距离问题(动态规划)

问题描述: 对于序列S和T, 它们之间的距离定义为: 对二者其一进行几次以下操作: 1, 删除一个字符; 2, 插入一个字符; 3, 改变一个字符. 每进行一次操作, 计

朴灿烈づ我的快乐病毒、/ 2022年04月23日 22:56/ 0 赞/ 397 阅读

相关动态规划之编辑距离问题*

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4

「爱情、让人受尽委屈。」/ 2022年04月22日 02:08/ 0 赞/ 308 阅读