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

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()){
            String str1 = in.nextLine();
            String str2 = in.nextLine();

            memo = new int[str1.length()+1][str2.length()+1];
            for(int[] arr : memo){
                Arrays.fill(arr,-1);
            }

            char[] chars1 = str1.toCharArray();
            char[] chars2 = str2.toCharArray();
            System.out.println(levenshtein(chars1,chars1.length,chars2,chars2.length));

        }

    }

    static int[][] memo;

    /**
     * 求chars1[0,i-1] char2[0,j-1]的编辑距离
     * @param chars1
     * @param i
     * @param chars2
     * @param j
     * @return
     */
    private static int levenshtein(char[] chars1,int i,char[] chars2,int j){
        if(i==0){
            return j;
        }
        if(j==0){
            return i;
        }
        if(memo[i][j] != -1){
            return memo[i][j];
        }
        //如果一样啥都不用做
        if(chars1[i-1] == chars2[j-1]){
            memo[i][j] = levenshtein(chars1,i-1,chars2,j-1);
        }else{
            //如果字符不一样，则有增删替换三种操作,编辑距离都是+1
            memo[i][j] =
                    min(levenshtein(chars1,i-1,chars2,j) + 1,//删除
                            levenshtein(chars1,i,chars2,j-1) + 1,//插入
                            levenshtein(chars1,i-1,chars2,j-1) + 1//替换
                    );
        }

        return memo[i][j];
    }
    private static int min(int a,int b,int c){
        return Math.min(Math.min(a,b),c);
    }
}