求2个字符串的最短编辑距离 java 实现

EditStepInfo.java：

import lombok.Getter;
import lombok.Setter;import java.io.Serializable;
import java.util.List;@Getter
@Setter
public class EditStepInfo implements Serializable {private String str1;private String str2;// str1和 str2 的最短编辑路基private int sed;private List<StepVO> steps;}

StepVO.java：

import lombok.Getter;
import lombok.Setter;import java.io.Serializable;@Getter
@Setter
public class StepVO implements Serializable {/*** 当前变换描述*/private String desc;private Character optChar1;private Character optChar2;/*** 当前变换成的字符串*/private String tempString;}

ShortestEditDistanceTest.java：

import java.util.ArrayList;
import java.util.List;public class ShortestEditDistanceTest {private static EditStepInfo[][] MAT_SED = null;public static void main(String[] args) {//   m o t h e r//   m o n s t e rString string1 = "mother";String string2 = "monster";MAT_SED = new EditStepInfo[ string1.length() ][ string2.length() ];EditStepInfo editStepInfo = calculateShortestEditDistance(string1, string2);System.out.println( string1 );System.out.println( string2 );System.out.println( "最小编辑距离：" + editStepInfo.getSed() );System.out.println( "编辑步骤：" );List<String> steps = editStepInfo.getSteps();for( String step:steps ){System.out.println( step );}}private static EditStepInfo calculateShortestEditDistance( String string1,String string2 ){if( string1 == null || string1.length() == 0 ){EditStepInfo editStepInfo = new EditStepInfo();editStepInfo.setStr1( string1 );editStepInfo.setStr2( string2 );editStepInfo.setSed( string2.length() );return editStepInfo;}if( string2 == null || string2.length() == 0){EditStepInfo editStepInfo = new EditStepInfo();editStepInfo.setStr1( string1 );editStepInfo.setStr2( string2 );editStepInfo.setSed( string1.length() );return editStepInfo;}int len1 = string1.length();int len2 = string2.length();for( int i=0;i<len1;i++ ){String str1 = string1.substring(0, i + 1);for( int j=0;j<len2;j++ ){String str2 = string2.substring(0, j + 1);EditStepInfo editStepInfo = new EditStepInfo();editStepInfo.setStr1( str1 );editStepInfo.setStr2( str2 );if( str1.length() == 1 ){if( str2.length() == 1 ){if( str1.equals( str2 ) ){// str1 和 str2 的长度均为1，并且 str1 和 str2 相等// a// aeditStepInfo.setSed( 0 );}else {// str1 和 str2 的长度均为1，并且 str1 和 str2 不相等// a// bList<StepVO> steps = new ArrayList<>();StepVO step = new StepVO();step.setDesc( "将 " + str1 + " 修改为 " + str2 );step.setTempString( str2 );steps.add( step );editStepInfo.setSteps( steps );editStepInfo.setSed( steps.size() );}}else {if( str2.contains( str1 ) ){// str1 的长度为1，str2 的长度大于1，并且 str1 在 str2 中不出现//   a// ..a...//  组装编辑步骤信息List<StepVO> steps = buildEditSteps(  str1.charAt(0),str2 );editStepInfo.setSteps( steps );editStepInfo.setSed( steps.size() );}else {// str1 的长度为1，str2的长度大于1，并且str1在 str2中不存在//   a// ..b...//  组装编辑步骤信息List<StepVO> steps = buildEditSteps(str1.charAt(0), str2);editStepInfo.setSteps( steps );editStepInfo.setSed( steps.size() );}}}else {if( str2.length() == 1 ){if( str1.contains( str2 ) ){// ...a..//    a//  组装编辑步骤信息List<String> steps = buildEditSteps(str1, str2.charAt(0));editStepInfo.setSteps( steps );editStepInfo.setSed( steps.size() );}else {// ...b..//    a//  组装编辑步骤信息List<String> steps = buildEditSteps(str1, str2.charAt(0));editStepInfo.setSteps( steps );editStepInfo.setSed( steps.size() );}}else {Character lastChar1 = getLastChar(str1);Character lastChar2 = getLastChar(str2);if( lastChar1.equals( lastChar2 ) ){//    ------a// ---------a//  组装编辑步骤信息EditStepInfo editStepInfo_prev = MAT_SED[i - 1][j - 1];List<String> steps = new ArrayList<>();List<String> steps_prev = editStepInfo_prev.getSteps();if( steps_prev != null ){steps.addAll( steps_prev );}editStepInfo.setSteps( steps );editStepInfo.setSed( steps.size() );}else {//    -----a// ........b// 1. str1 的 "-----" 部分转换为 str2，再删除 a// 2. str1 转换为 str2 的 "........" 部分，再添加 b// 3. str1 的 "-----" 部分转换为 str2 的 "........" 部分，再将a修改为 b// 求 方法1、2、3中选一个最小的编辑步骤作为最终的编辑步骤EditStepInfo editStepInfo_prev_1 = MAT_SED[i - 1][j];EditStepInfo editStepInfo_prev_2 = MAT_SED[i][j - 1];EditStepInfo editStepInfo_prev_3 = MAT_SED[i - 1][j - 1];EditStepInfo editStepInfo_prev_min = editStepInfo_prev_1;int minMethodNum = 1;if( editStepInfo_prev_2.getSed() < editStepInfo_prev_min.getSed() ){editStepInfo_prev_min = editStepInfo_prev_2;minMethodNum = 2;}if( editStepInfo_prev_3.getSed() < editStepInfo_prev_min.getSed() ){editStepInfo_prev_min = editStepInfo_prev_3;minMethodNum = 3;}List<String> steps = new ArrayList<>();List<String> steps_prev_min = editStepInfo_prev_min.getSteps();if( steps_prev_min != null ){steps.addAll( steps_prev_min );}if( minMethodNum == 1 ){steps.add( "删除 " + lastChar1 );}else if( minMethodNum == 2 ){steps.add( "添加 " + lastChar2 );}else if( minMethodNum == 3 ){steps.add( "修改 " + lastChar1 + " 为 " + lastChar2 );}editStepInfo.setSteps( steps );editStepInfo.setSed( steps.size() );}}}MAT_SED[ i ][ j ] = editStepInfo;}}return MAT_SED[ string1.length() - 1 ][ string2.length() - 1 ];}/*** 组装将字符 srcChar 转换成字符串 targetString 的编辑步骤* @param srcChar 例如：a* @param targetString 例如：bcdefg* @return*/private static List<StepVO> buildEditSteps(Character srcChar, String targetString) {boolean hasMeet = false;int length = targetString.length();List<StepVO> steps = new ArrayList<>();for( int i = 0;i < length;i++ ){Character char2 = targetString.charAt( i );if( hasMeet ){StepVO step = new StepVO();step.setDesc( "添加 " + char2 );step.setOptChar1( char2 );steps.add( step );}else {if( srcChar.equals( char2 ) ){// do nothinghasMeet = true;}else {StepVO step = new StepVO();step.setDesc( "添加 " + char2 );step.setOptChar1( char2 );steps.add( step );}}}if( !hasMeet ){// 此种情况只发生在 targetString 中不包含 srcChar 时StepVO step = new StepVO();step.setDesc( "删除 " + srcChar );step.setOptChar1( srcChar );steps.add( 0,step );}//  设置 每个步骤生成的  tempStringString tempString = String.valueOf( srcChar );for( StepVO step:steps ){String desc = step.getDesc();if( desc.startsWith( "删除" ) ){tempString = "";}else if( desc.startsWith( "添加" ) ){tempString += step.getOptChar1();}step.setTempString( tempString );}return steps;}private static List<StepVO> buildEditSteps(String srcString, Character targetChar) {// abcdefg// cboolean hasMeet = false;int length = srcString.length();List<StepVO> steps = new ArrayList<>();for( int i = 0;i < length;i++ ){Character char1 = srcString.charAt( i );if( hasMeet ){StepVO step = new StepVO();step.setDesc( "删除 " + char1 );step.setOptChar1( char1 );steps.add( step );}else {if( targetChar.equals( char1 ) ){// do nothinghasMeet  =true;}else {StepVO step = new StepVO();step.setDesc( "删除 " + char1 );step.setOptChar1( char1 );steps.add( step );}}}if( !hasMeet ){StepVO step = new StepVO();step.setDesc( "添加 " + targetChar );step.setOptChar1( targetChar );steps.add( 0,step );}// todo 生成 tempStringString tempString = srcString;for( StepVO step:steps ){String desc = step.getDesc();if( desc.startsWith( "添加" ) ){}else if( desc.startsWith( "删除" ) ){}step.setTempString( null );}return steps;}private static Character getLastChar(String str) {if( str == null || str.length() == 0 ){return null;}return  str.charAt(str.length() - 1);}
}

mother
monster
最小编辑距离：3
编辑步骤：
添加 n
添加 s
删除 h