求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 r String 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 // a editStepInfo.setSed( 0 ); }else { // str1 和 str2 的长度均为1，并且 str1 和 str2 不相等 // a // b List<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 nothing hasMeet = 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 ); } // 设置 每个步骤生成的 tempString String 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 // c boolean 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 nothing hasMeet =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 生成 tempString String 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