题目

给定2个字符串，计算一个字符串经过最少的变换转换为另外一个字符串。 变换可以是3种： 插入一个字符 删除一个字符 更改一个字符

例如： str = “abc” str2 = “bc” str删除前边的一个字符则变成str2，或者str2增加一个字符则变成str，所以编辑距离为1

分析思路

动态规划思想 字符串A，字符串B编辑距离和 字符串A去掉最后1个字符，字符串B去掉最后1个字符 字符串A，字符串B去掉最后1个字符 字符串A去掉最后1个字符，字符串B 的相似度有一定的关系，可以得到迭代公式，进一步进行计算即可

代码

package org.example.distance; /** * 最短编辑距离 */ public class EditDistance { //初始化数据 public static int editDistance(char[] strA,char[] strB){ int[][] dp = new int[strA.length+1][strB.length+1]; //初始化 for (int i = 0; i < strA.length+1 ; i++) { dp[i][0]=i; } //初始化 for (int j = 0; j < strB.length+1 ; j++) { dp[0][j]=j; } //计算最短编辑距离 //从矩阵的左下角开始计算最小编辑距离 for (int i = 1; i < strA.length+1 ; i++) { for (int j = 1; j < strB.length+1; j++) { //如果末尾字符一样 if(strA[i-1]==strB[j-1]){ dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])+1); }else { dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1; } } } //返回编辑距离 return dp[strA.length][strB.length]; } public static void main(String[] args) { char[] strA = "abcd".toCharArray(); char[] strB = "ab".toCharArray(); System.out.println(editDistance(strA,strB)); } }