package springboot.chapter2;
import java.util.*;
//System.out.println(Integer.toBinaryString(10));
public class Test {
public static void main(String[] args) {
Scanner in = new Scanner(System.in); while(in.hasNext()){ String str1 = in.nextLine(); String str2 = in.nextLine(); System.out.println(LevenshteinDistance(str1, str2)); } } public static int LevenshteinDistance(String str1,String str2) { int x = str1.length(); int y =str2.length(); int[][] temp = new int[y+1][x+1]; //初始化由空变到XY坐标的值 for (int i = 0; i <=y ; i++) { temp[i][0]=i; } for (int i = 0; i < x; i++) { temp[0][i]=i; } for (int i = 1; i < y+1 ; i++) { for (int j = 1; j < x+1 ; j++) { if (str2.charAt(i-1)==str1.charAt(j-1)) temp[i][j]=temp[i-1][j-1]; else temp[i][j]=Math.min(Math.min(temp[i-1][j],temp[i][j-1]),temp[i-1][j-1])+1; } } return temp[y][x]; }
}