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];
}

}