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

/**
 * 编辑距离
 */
public class Main {
    static String s1;
    static String s2;
    static Integer[][] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s1 = sc.nextLine();
        s2 = sc.nextLine();
        int length1 = s1.length();
        int length2 = s2.length();
        arr = new Integer[length1 + 1][length2 + 1];
        for (int i = 0; i <=s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                arr[i][j] = editDistance(i, j);
            }
        }
         System.out.println(arr[length1][length2]);
    }

    private static int editDistance(int length1, int length2) {
        if(arr[length1][length2] != null){
            return arr[length1][length2];
        }
        if (length1 == 0) {
            return length2;
        }
        if (length2 == 0) {
            return length1;
        }
        if (s1.charAt(length1 - 1) == s2.charAt(length2 - 1)) {
            return editDistance(length1 - 1, length2 - 1);
        } else {
            int n1 = editDistance(length1 - 1, length2 - 1) + 1; // 改变 都去掉最后一位
            int n2 = editDistance(length1 - 1, length2) + 1; //s1去掉一个或者S2加一个
            int n3 = editDistance(length1, length2 - 1) + 1; //s2去掉一个或者S1加一个
            return Math.min(n1, Math.min(n2, n3));
        }
    }
}