题解 | #计算字符串的编辑距离#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        // 注意 hasNext 和 hasNextLine 的区别

        while (in.hasNext()) { 

            String a = in.next();

            String b = in.next();

            System.out.println(getMinIns(a,b));

        }

    }

    private static int getMinIns(String s1,String s2){

        int[][] dp = new int[s1.length()+1][s2.length()+1];//定义一个二维数组存放历史数据

        for(int i=1;i<dp.length;i++){

            dp[i][0] = i;//当一个字符串长度为0时，另一份长度就是此时的最小距离了

        }

        //同理搞出递归的另一个

        for(int i=1;i<dp[0].length;i++){

            dp[0][i] = i;

        }

        //递归出口，明显s1和s2长度都为0时，距离为0

        dp[0][0] = 0;

        for(int i=1;i<dp.length;i++){

            for(int j=1;j<dp[i].length;j++){

                if(s1.charAt(i-1)==s2.charAt(j-1)){

                    dp[i][j] = dp[i-1][j-1];

                }else{

                    //替换和s1删除1个字符串，最小距离

                    int min1 = Math.min(dp[i-1][j-1]+1,dp[i-1][j]+1);

                    //替换和s2删除1个字符串，最小距离

                    int min2 = Math.min(dp[i-1][j-1]+1,dp[i][j-1]+1);

                    dp[i][j] = Math.min(min1,min2);

                }

            }  

        }

        return dp[s1.length()][s2.length()];       

    }

}