// Leetcode 72题 编辑距离 package kuaishou; import java.util.Scanner; //public class Main { public class LevenshteinDistance {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         while (in.hasNext()) {             String a = in.nextLine();             String b = in.nextLine();             if(a == null || a.length() == 0){                 if(b == null || b.length() == 0)                     System.out.println(0);                 else                     System.out.println(b.length());             }             else if(b == null || b.length() == 0){                 System.out.println(a.length());             }else{                 int [][] distance = new int [a.length()+1][b.length()+1];                 for(int i=0; i<=a.length(); i++)                     distance[i][0] = i;                 for(int i=0; i<=b.length(); i++)                     distance[0][i] = i;                 for(int i=1; i<=a.length(); i++){                     for(int j=1; j<=b.length(); j++){                         int min1, min2;                         if(a.charAt(i-1) == b.charAt(j-1))                             min1 = distance[i-1][j-1];                         else                             min1 = distance[i-1][j-1] + 1;                         min2 = Math.min(distance[i][j-1]+1, distance[i-1][j]+1);                         distance[i][j] = Math.min(min1, min2);                     }                 }                 System.out.println(distance[a.length()][b.length()]);             }         }     } }