public static int minDistance(String word1,String word2){
  if (word1.equals(word2))   return 0;
  int m=word1.length();
  int n=word2.length();
  int[][] d=new int[m + 1][n + 1];
  d[0][0]=0;
  for (int i=1; i < m + 1; i++)   d[i][0]=i;
  for (int j=1; j < n + 1; j++)   d[0][j]=j;
  for (int i=1; i < m + 1; i++) {
    for (int j=1; j < n + 1; j++) {
      d[i][j]=Math.min(Math.min(d[i][j - 1] + 1,d[i - 1][j] + 1),word1.charAt(i - 1) == word2.charAt(j - 1) ? d[i - 1][j - 1] : d[i - 1][j - 1] + 1);
    }
  }
  return d[m][n];
}

public static int minDistance ( String word1 , String word2 ) { if ( word1 . equals ( word2 ) ) return 0 ; int m = word1 . length ( ) ; int n = word2 . length ( ) ; int [ ] [ ] d = new int [ m + 1 ] [ n + 1 ] ; d [ 0 ] [ 0 ] = 0 ; for ( int i = 1 ; i < m + 1 ; i ++ ) d [ i ] [ 0 ] = i ; for ( int j = 1 ; j < n + 1 ; j ++ ) d [ 0 ] [ j ] = j ; for ( int i = 1 ; i < m + 1 ; i ++ ) { for ( int j = 1 ; j < n + 1 ; j ++ ) { d [ i ] [ j ] = Math . min ( Math . min ( d [ i ] [ j - 1 ] + 1 , d [ i - 1 ] [ j ] + 1 ) , word1 . charAt ( i - 1 ) == word2 . charAt ( j - 1 ) ? d [ i - 1 ] [ j - 1 ] : d [ i - 1 ] [ j - 1 ] + 1 ) ; } } return d [ m ] [ n ] ; }
dp , o ( nm ) time , o ( nm ) space searching for a path ( sequence of edits ) from the start string to the final string for two strings , x of length n , y of length m define d ( i , j ) : the edit distance between x [ 1 . . i ] and y [ 1 . . j ] the edit distance between x and y is thus d ( n , m ) initialization : d ( i , 0 ) = i , d ( 0 , j ) = j 1 . d ( i , j ) = min ( d ( i - 1 , j ) + 1 , d ( i , j - 1 ) + 1 , d ( i - 1 , j - 1 ) + 0 or 1 ) , 0 is x ( i ) = y ( j ) , 1 if x ( i ) ! = y ( j ) d ( n , m ) is distance note that f [ i ] [ j ] only depends on f [ i - 1 ] [ j - 1 ] , f [ i - 1 ] [ j ] and f [ i ] [ j - 1 ] , therefore we can reduce the space to o ( n ) by using only the ( i - 1 ) th array and previous updated element ( f [ i ] [ j - 1 ] ) .
