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

    EditStepInfo.java：
    1.  
    2.  
    3. import lombok.Getter;
    4. import lombok.Setter;
    5.  
    6. import java.io.Serializable;
    7. import java.util.List;
    8.  
    9.  
    10. @Getter
    11. @Setter
    12. public class EditStepInfo implements Serializable {
    13.  
    14.     private String str1;
    15.     private String str2;
    16.  
    17.     // str1和 str2 的最短编辑路基
    18.     private int sed;
    19.  
    20.     private List steps;
    21.  
    22.  
    23.     private String tempString;
    24.  
    25.  
    26. }

    StepVO.java：
    1.  
    2.  
    3. import lombok.Getter;
    4. import lombok.Setter;
    5.  
    6. import java.io.Serializable;
    7.  
    8.  
    9. @Getter
    10. @Setter
    11. public class StepVO implements Serializable {
    12.  
    13.     public static final String OPT_TYPE_ADD = "add";
    14.     public static final String OPT_TYPE_DELETE = "delete";
    15.     public static final String OPT_TYPE_UPDATE = "UPDATE";
    16.  
    17.     /**
    18.      * 当前变换描述
    19.      */
    20.     private String desc;
    21.  
    22.     private int optIndex;
    23.  
    24.     private Character optChar1;
    25.     private Character optChar2;
    26.  
    27.     private String optType;
    28.  
    29.     /**
    30.      * 当前变换成的字符串
    31.      */
    32.     private String tempString;
    33.  
    34.     public static void main(String[] args) {
    35.         String s = "abcdf";
    36.         Character c = s.charAt(0);
    37.         System.out.println( c.toString() );
    38.     }
    39.  
    40. }

    ShortestEditDistanceTest.java：
    1.  
    2.  
    3. import java.util.ArrayList;
    4. import java.util.List;
    5.  
    6.  
    7. public class ShortestEditDistanceTest {
    8.  
    9.     private static EditStepInfo[][] MAT_SED = null;
    10.  
    11.     public static void main(String[] args) {
    12.         //   m o t h e r
    13.         //   m o n s t e r
    14.         String string1 = "calculate";
    15.         String string2 = "caketakes";
    16.         MAT_SED = new EditStepInfo[ string1.length() ][ string2.length() ];
    17.         calculateShortestEditDistance(string1, string2);
    18.  
    19.         for( int i=0;i
    20.             for (int j = 0; j < string2.length(); j++) {
    21.                 EditStepInfo editStepInfo = MAT_SED[i][j];
    22.                 printEditStepInfo( editStepInfo );
    23.                 System.out.println();
    24.                 System.out.println();
    25.             }
    26.         }
    27.     }
    28.  
    29.     private static void printEditStepInfo(EditStepInfo editStepInfo) {
    30.         System.out.println( editStepInfo.getStr1() + " 到 " + editStepInfo.getStr2() + " 的最小编辑距离：" + editStepInfo.getSed() );
    31.         System.out.println( "编辑步骤：" );
    32.         List steps = editStepInfo.getSteps();
    33.         if( steps == null || steps.size() == 0 ){
    34.             System.out.println( "\ttempString = " + editStepInfo.getTempString() );
    35.         }else {
    36.             String tempString = editStepInfo.getStr1();
    37.             for( StepVO step:steps ){
    38.                 String optType = step.getOptType();
    39.                 int optIndex = step.getOptIndex();
    40.                 Character optChar1 = step.getOptChar1();
    41.                 if( StepVO.OPT_TYPE_ADD.equals( optType ) ){
    42.                     // 新增
    43.                     // 0 1 2 3 4
    44.                     tempString = addChar2String( tempString,optChar1,optIndex );
    45.                 }else if( StepVO.OPT_TYPE_DELETE.equals( optType ) ){
    46.                     // 删除
    47.                     // tempString = removeCharacter( tempString,optIndex );
    48.                     tempString = updateCharacterInString( tempString,optIndex,' ' );
    49.                 }else if( StepVO.OPT_TYPE_UPDATE.equals( optType ) ){
    50.                     // 修改
    51.                     Character optChar2 = step.getOptChar2();
    52.                     tempString = updateCharacterInString( tempString,optIndex,optChar2 );
    53.                 }
    54.                 System.out.println( "\t" + step.getDesc() + "：" + tempString  + " optIndex = " + optIndex);
    55.             }
    56.         }
    57.     }
    58.  
    59.     private static String updateCharacterInString(String str, int updateIndex, Character character) {
    60.         // 01234
    61.         if( updateIndex < 0  ){
    62.             updateIndex = 0;
    63.         }else if( updateIndex >= str.length() ){
    64.             updateIndex = str.length() - 1;
    65.         }
    66.         int length = str.length();
    67.         String str_result = "";
    68.         for( int i=0;i
    69.             char c = str.charAt(i);
    70.             if( i == updateIndex ){
    71.                 str_result += character;
    72.             }else {
    73.                 str_result += c;
    74.             }
    75.         }
    76.         return str_result;
    77.     }
    78.  
    79.     private static String removeCharacter(String str,int removeIndex) {
    80.         // 01234
    81.         if( removeIndex < 0 ){
    82.             removeIndex = 0;
    83.         }
    84.         if( removeIndex >= str.length() ){
    85.             removeIndex = str.length() - 1;
    86.         }
    87.         if( removeIndex == 0 ){
    88.             return str.substring( 1 );
    89.         }else if( removeIndex == str.length() - 1 ){
    90.             return str.substring( 0,removeIndex );
    91.         }else {
    92.             return str.substring( 0,removeIndex  ) + str.substring( removeIndex + 1 );
    93.         }
    94.     }
    95.  
    96.     private static String addChar2String(String str,Character character, int addIndex) {
    97.         if( addIndex > str.length() ){
    98.             addIndex = str.length();
    99.         }
    100.         return str.substring( 0,addIndex ) + character + str.substring( addIndex );
    101.     }
    102.  
    103.     private static EditStepInfo calculateShortestEditDistance( String string1,String string2 ){
    104.         if( string1 == null || string1.length() == 0 ){
    105.             EditStepInfo editStepInfo = new EditStepInfo();
    106.             editStepInfo.setStr1( string1 );
    107.             editStepInfo.setStr2( string2 );
    108.             editStepInfo.setSed( string2.length() );
    109.             return editStepInfo;
    110.         }
    111.         if( string2 == null || string2.length() == 0){
    112.             EditStepInfo editStepInfo = new EditStepInfo();
    113.             editStepInfo.setStr1( string1 );
    114.             editStepInfo.setStr2( string2 );
    115.             editStepInfo.setSed( string1.length() );
    116.             return editStepInfo;
    117.         }
    118.         int len1 = string1.length();
    119.         int len2 = string2.length();
    120.         for( int i=0;i
    121.             String str1 = string1.substring(0, i + 1);
    122.             for( int j=0;j
    123.                 String str2 = string2.substring(0, j + 1);
    124.  
    125.                 EditStepInfo editStepInfo = new EditStepInfo();
    126.                 editStepInfo.setStr1( str1 );
    127.                 editStepInfo.setStr2( str2 );
    128.                 if( str1.length() == 1 ){
    129.                     if( str2.length() == 1 ){
    130.                         if( str1.equals( str2 ) ){
    131.                             // str1 和 str2 的长度均为1，并且 str1 和 str2 相等
    132.                             // a
    133.                             // a
    134.                             List steps = new ArrayList<>();
    135.                             editStepInfo.setSteps( steps );
    136.                             editStepInfo.setTempString( str1 );
    137.                             editStepInfo.setSed( steps.size() );
    138.                         }else {
    139.                             // str1 和 str2 的长度均为1，并且 str1 和 str2 不相等
    140.                             // a
    141.                             // b
    142.                             List steps = new ArrayList<>();
    143.                             StepVO step = new StepVO();
    144.                             step.setDesc( "将 " + str1 + " 修改为 " + str2 );
    145.                             step.setTempString( str2 );
    146.                             step.setOptType( StepVO.OPT_TYPE_UPDATE );
    147.                             step.setOptChar1( str1.charAt( 0 ) );
    148.                             step.setOptIndex( 0 );
    149.                             step.setOptChar2( str2.charAt( 0 ) );
    150.                             steps.add( step );
    151.                             editStepInfo.setSteps( steps );
    152.                             editStepInfo.setTempString( getLastTempString( steps ) );
    153.                             editStepInfo.setSed( steps.size() );
    154.                         }
    155.                     }else {
    156.                         if( str2.contains( str1 ) ){
    157.                             // str1 的长度为1，str2 的长度大于1，并且 str1 在 str2 中出现
    158.                             //   a
    159.                             // ..a...
    160.                             //  组装编辑步骤信息
    161.                             List steps = buildEditSteps(  str1.charAt(0),str2 );
    162.                             editStepInfo.setSteps( steps );
    163.                             editStepInfo.setTempString( getLastTempString( steps ) );
    164.                             editStepInfo.setSed( steps.size() );
    165.                         }else {
    166.                             // str1 的长度为1，str2的长度大于1，并且str1在 str2中不存在
    167.                             //   a
    168.                             // ..b...
    169.                             //  组装编辑步骤信息
    170.                             List steps = buildEditSteps(str1.charAt(0), str2);
    171.                             editStepInfo.setSteps( steps );
    172.                             editStepInfo.setTempString( getLastTempString( steps ) );
    173.                             editStepInfo.setSed( steps.size() );
    174.                         }
    175.                     }
    176.                 }else {
    177.                     if( str2.length() == 1 ){
    178.                         if( str1.contains( str2 ) ){
    179.                             // ...a..
    180.                             //    a
    181.                             //  组装编辑步骤信息
    182.                             List steps = buildEditSteps(str1, str2.charAt(0));
    183.                             editStepInfo.setSteps( steps );
    184.                             editStepInfo.setTempString( getLastTempString( steps ) );
    185.                             editStepInfo.setSed( steps.size() );
    186.                         }else {
    187.                             // ...b..
    188.                             //    a
    189.                             //  组装编辑步骤信息
    190.                             List steps = buildEditSteps(str1, str2.charAt(0));
    191.                             editStepInfo.setSteps( steps );
    192.                             editStepInfo.setTempString( getLastTempString( steps ) );
    193.                             editStepInfo.setSed( steps.size() );
    194.                         }
    195.                     }else {
    196.                         Character lastChar1 = getLastChar(str1);
    197.                         Character lastChar2 = getLastChar(str2);
    198.                         if( lastChar1.equals( lastChar2 ) ){
    199.                             //    ------a
    200.                             // ---------a
    201.                             //  组装编辑步骤信息
    202.                             EditStepInfo editStepInfo_prev = MAT_SED[i - 1][j - 1];
    203.                             List steps = new ArrayList<>();
    204.                             List steps_prev = editStepInfo_prev.getSteps();
    205.                             String tempString = editStepInfo_prev.getTempString() + lastChar1;
    206.                             if( steps_prev != null ){
    207.                                 steps.addAll( steps_prev );
    208.                             }
    209.                             editStepInfo.setSteps( steps );
    210.                             editStepInfo.setTempString( tempString );
    211.                             editStepInfo.setSed( steps.size() );
    212.                         }else {
    213.                             //    ----- a
    214.                             // ........ b
    215.                             // 1. str1 的 "-----" 部分转换为 str2，再删除 a
    216.                             // 2. str1 转换为 str2 的 "........" 部分，再添加 b
    217.                             // 3. str1 的 "-----" 部分转换为 str2 的 "........" 部分，再将a修改为 b
    218.                             // 求 方法1、2、3中选一个最小的编辑步骤作为最终的编辑步骤
    219.                             EditStepInfo editStepInfo_prev_1 = MAT_SED[i - 1][j];
    220.                             EditStepInfo editStepInfo_prev_2 = MAT_SED[i][j - 1];
    221.                             EditStepInfo editStepInfo_prev_3 = MAT_SED[i - 1][j - 1];
    222.                             EditStepInfo editStepInfo_prev_min = editStepInfo_prev_1;
    223.                             int minMethodNum = 1;
    224.                             if( editStepInfo_prev_2.getSed() < editStepInfo_prev_min.getSed() ){
    225.                                 editStepInfo_prev_min = editStepInfo_prev_2;
    226.                                 minMethodNum = 2;
    227.                             }
    228.                             if( editStepInfo_prev_3.getSed() < editStepInfo_prev_min.getSed() ){
    229.                                 editStepInfo_prev_min = editStepInfo_prev_3;
    230.                                 minMethodNum = 3;
    231.                             }
    232.                             List steps = new ArrayList<>();
    233.                             List steps_prev_min = editStepInfo_prev_min.getSteps();
    234.                             if( steps_prev_min != null ){
    235.                                 steps.addAll( steps_prev_min );
    236.                             }
    237.                             StepVO step_last = null;
    238.                             if( steps.size() > 0 ){
    239.                                 step_last = steps.get(steps.size() - 1);
    240.                             }
    241.                             String tempString = editStepInfo_prev_min.getTempString();
    242.                             StepVO step = new StepVO();
    243.                             if( minMethodNum == 1 ){
    244.                                 step.setDesc( "删除 " + lastChar1 );
    245.                                 step.setOptType( StepVO.OPT_TYPE_DELETE );
    246.                                 step.setOptChar1( lastChar1 );
    247.                                 step.setOptIndex( str1.length() - 1 );
    248.                                 // todo 估计有问题？？？
    249.                                 step.setTempString( tempString );
    250.                             }else if( minMethodNum == 2 ){
    251.                                 step.setDesc( "添加 " + lastChar2 );
    252.                                 step.setOptType( StepVO.OPT_TYPE_ADD );
    253.                                 step.setOptChar1( lastChar2 );
    254.                                 if( step_last != null ){
    255.                                     step.setOptIndex( step_last.getOptIndex() + 1 );
    256.                                 }else {
    257.                                     step.setOptIndex( str1.length() );
    258.                                 }
    259.                                 // todo 估计有问题？？？
    260.                                 step.setTempString( tempString + lastChar2 );
    261.                             }else if( minMethodNum == 3 ){
    262.                                 step.setDesc( "修改 " + lastChar1 + " 为 " + lastChar2 );
    263.                                 step.setOptType( StepVO.OPT_TYPE_UPDATE );
    264.                                 step.setOptChar1( lastChar1 );
    265.                                 step.setOptChar2( lastChar2 );
    266.                                 step.setOptIndex( str1.length() - 1 );
    267.                                 // todo 估计有问题？？？
    268.                                 step.setTempString( tempString + lastChar2 );
    269.                             }
    270.                             steps.add( step );
    271.                             editStepInfo.setSteps( steps );
    272.                             editStepInfo.setTempString( tempString );
    273.                             editStepInfo.setSed( steps.size() );
    274.                         }
    275.                     }
    276.                 }
    277.                 MAT_SED[ i ][ j ] = editStepInfo;
    278.             }
    279.         }
    280.         return MAT_SED[ string1.length() - 1 ][ string2.length() - 1 ];
    281.     }
    282.  
    283.     private static String getLastTempString(List steps) {
    284.         if( steps == null || steps.size() == 0 ){
    285.             return null;
    286.         }
    287.         return steps.get( steps.size() - 1 ).getTempString();
    288.     }
    289.  
    290.     /**
    291.      * 组装将字符 srcChar 转换成字符串 targetString 的编辑步骤
    292.      * @param srcChar 例如：a
    293.      * @param targetString 例如：bcdefg
    294.      * @return
    295.      */
    296.     private static List buildEditSteps(Character srcChar, String targetString) {
    297.         boolean hasMeet = false;
    298.         int length = targetString.length();
    299.         List steps = new ArrayList<>();
    300.         for( int i = 0;i < length;i++ ){
    301.             Character char2 = targetString.charAt( i );
    302.             if( hasMeet ){
    303.                 StepVO step = new StepVO();
    304.                 step.setDesc( "添加 " + char2 );
    305.                 step.setOptChar1( char2 );
    306.                 step.setOptIndex( i );
    307.                 step.setOptType( StepVO.OPT_TYPE_ADD );
    308.                 steps.add( step );
    309.             }else {
    310.                 if( srcChar.equals( char2 ) ){
    311.                     // do nothing
    312.                     hasMeet = true;
    313.                 }else {
    314.                     StepVO step = new StepVO();
    315.                     step.setDesc( "添加 " + char2 );
    316.                     step.setOptChar1( char2 );
    317.                     step.setOptIndex( i );
    318.                     step.setOptType( StepVO.OPT_TYPE_ADD );
    319.                     steps.add( step );
    320.                 }
    321.             }
    322.         }
    323.         if( !hasMeet ){
    324.             // 此种情况只发生在 targetString 中不包含 srcChar 时
    325.             StepVO step = new StepVO();
    326.             step.setDesc( "删除 " + srcChar );
    327.             step.setOptChar1( srcChar );
    328.             step.setOptIndex( 0 );
    329.             step.setOptType( StepVO.OPT_TYPE_DELETE );
    330.             steps.add( 0,step );
    331.         }
    332.         //  设置 每个步骤生成的  tempString
    333.         String tempString = String.valueOf( srcChar );
    334.         for( StepVO step:steps ){
    335.             String optType = step.getOptType();
    336.             Character optChar1 = step.getOptChar1();
    337.             if( StepVO.OPT_TYPE_DELETE.equals( optType ) ){
    338.                 tempString = tempString.replaceFirst( optChar1.toString(),"" );
    339.             }else if( StepVO.OPT_TYPE_ADD.equals( optType ) ){
    340.                 tempString += optChar1;
    341.             }
    342.             step.setTempString( tempString );
    343.         }
    344.         return steps;
    345.     }
    346.  
    347.     private static List buildEditSteps(String srcString, Character targetChar) {
    348.         // abcdefg
    349.         // c
    350.         boolean hasMeet = false;
    351.         int length = srcString.length();
    352.         List steps = new ArrayList<>();
    353.         for( int i = 0;i < length;i++ ){
    354.             Character char1 = srcString.charAt( i );
    355.             if( hasMeet ){
    356.                 StepVO step = new StepVO();
    357.                 step.setDesc( "删除 " + char1 );
    358.                 step.setOptChar1( char1 );
    359.                 step.setOptIndex( i );
    360.                 step.setOptType( StepVO.OPT_TYPE_DELETE );
    361.                 steps.add( step );
    362.             }else {
    363.                 if( targetChar.equals( char1 ) ){
    364.                     // do nothing
    365.                     hasMeet  =true;
    366.                 }else {
    367.                     StepVO step = new StepVO();
    368.                     step.setDesc( "删除 " + char1 );
    369.                     step.setOptChar1( char1 );
    370.                     step.setOptIndex( i );
    371.                     step.setOptType( StepVO.OPT_TYPE_DELETE );
    372.                     steps.add( step );
    373.                 }
    374.             }
    375.         }
    376.         if( !hasMeet ){
    377.             StepVO step = new StepVO();
    378.             step.setDesc( "添加 " + targetChar );
    379.             step.setOptChar1( targetChar );
    380.             step.setOptIndex( 0 );
    381.             step.setOptType( StepVO.OPT_TYPE_ADD );
    382.             steps.add( 0,step );
    383.         }
    384.         String tempString = srcString;
    385.         for( StepVO step:steps ){
    386.             String optType = step.getOptType();
    387.             Character optChar1 = step.getOptChar1();
    388.             if( StepVO.OPT_TYPE_ADD.equals( optType ) ){
    389.                 tempString += optChar1;
    390.             }else if( StepVO.OPT_TYPE_DELETE.equals( optType ) ){
    391.                 tempString = tempString.replaceFirst( optChar1.toString(),"" );
    392.             }
    393.             step.setTempString( tempString );
    394.         }
    395.         return steps;
    396.     }
    397.  
    398.  
    399.     private static Character getLastChar(String str) {
    400.         if( str == null || str.length() == 0 ){
    401.             return null;
    402.         }
    403.         return  str.charAt(str.length() - 1);
    404.     }
    405. }

    1. mother
    2. monster
    3. 最小编辑距离：3
    4. 编辑步骤：
    5. 添加 n
    6. 添加 s
    7. 删除 h

  • 相关阅读:
    服装PLM解决方案能带给企业什么？
    网络安全：MSF常用命令总结
    mysql-MVCC
    【前端工程化】使用jest单元测试，提高效率的方法
    自定义注解和@Target、@Retention注解的使用
    开题报告不知道怎么写？
    webpack拓展篇（六十八）：bundle 和 bundless 的差异
    计算机系统（23）--- 死锁的处理策略
    Linux下安装MySQL
    Pinely Round 1 (Div. 1 + Div. 2) E - Make It Connected思维&&分类讨论
  • 原文地址：https://blog.csdn.net/heshiyuan1406146854/article/details/134272488