package com.fishercoder.solutions;

/**
 * 72. Edit Distance
 * Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

 You have the following 3 operations permitted on a word:

 a) Insert a character
 b) Delete a character
 c) Replace a character*/

public class _72 {

    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        if (m == 0) {
            return n;
        }
        if (n == 0) {
            return m;
        }

        char[] str1 = word1.toCharArray();
        char[] str2 = word2.toCharArray();

        int[][] table = new int[m + 1][n + 1];
        for (int i = 0; i < m + 1; i++) {
            table[i][0] = i;
        }
        for (int j = 0; j < n + 1; j++) {
            table[0][j] = j;
        }

        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                int cost = 0;
                if (str1[i - 1] != str2[j - 1]) {
                    cost = 1;
                }
                table[i][j] = Math.min(Math.min(table[i - 1][j] + 1, table[i][j - 1] + 1), table[i - 1][j - 1] + cost);
            }
        }

        return table[m][n];
    }

}

@@ -54,16 +54,19 @@
 istance%0A
+ *%0A
  * Given
@@ -92,16 +92,19 @@
 d word2,
+%0A *
  find th
@@ -164,16 +164,19 @@
 o word2.
+%0A *
  (each o
@@ -336,16 +336,18 @@
 haracter
+%0A 
 */%0A%0Apubl
@@ -362,16 +362,56 @@
  _72 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -463,24 +463,28 @@
 ) %7B%0A        
+    
 int m = word
@@ -499,24 +499,28 @@
 ();%0A        
+ 
+   
 int n = word
@@ -535,24 +535,28 @@
 ();%0A        
+   
+ 
 if (m == 0) 
@@ -549,32 +549,36 @@
   if (m == 0) %7B%0A
+    
             retu
@@ -591,26 +591,33 @@
         
-%7D%0A
+    %7D%0A   
         
 if (n ==
@@ -604,24 +604,25 @@
 %0A           
+ 
 if (n == 0) 
@@ -615,32 +615,36 @@
   if (n == 0) %7B%0A
+    
             retu
@@ -657,27 +657,32 @@
         
-%7D%0A%0A
+    %7D%0A  
         
 char%5B%5D s
@@ -665,32 +665,34 @@
     %7D%0A          
+  
 char%5B%5D str1 = wo
@@ -706,24 +706,28 @@
 harArray();%0A
+    
         char
@@ -766,16 +766,20 @@
         
+    
 int%5B%5D%5B%5D 
@@ -809,32 +809,36 @@
 n + 1%5D;%0A        
+  
+  
 for (int i = 0; 
@@ -859,32 +859,36 @@
 ) %7B%0A            
+    
 table%5Bi%5D%5B0%5D = i;
@@ -896,26 +896,33 @@
         
-%7D%0A
+    %7D%0A   
         
 for (int
@@ -905,32 +905,33 @@
    %7D%0A           
+ 
 for (int j = 0; 
@@ -956,24 +956,28 @@
             
+    
 table%5B0%5D%5Bj%5D 
@@ -981,35 +981,42 @@
 j%5D = j;%0A        
-%7D%0A%0A
+    %7D%0A    
         for (int
@@ -1033,32 +1033,36 @@
 %3C m + 1; i++) %7B%0A
+    
             for 
@@ -1103,24 +1103,28 @@
             
+    
 int cost = 0
@@ -1137,24 +1137,28 @@
             
+  
+  
 if (str1%5Bi -
@@ -1199,16 +1199,20 @@
         
+    
 cost = 1
@@ -1221,34 +1221,40 @@
                 
-%7D%0A
+    %7D%0A  
                 
@@ -1245,32 +1245,34 @@
                 
+  
 table%5Bi%5D%5Bj%5D = Ma
@@ -1329,16 +1329,40 @@
 1%5D + 1),
+%0A                       
  table%5Bi
@@ -1387,32 +1387,36 @@
 t);%0A            
+    
 %7D%0A        %7D%0A%0A   
@@ -1413,19 +1413,23 @@
     
+ 
+   
 %7D%0A
-%0A
+ 
         
 retu
@@ -1420,24 +1420,27 @@
  %7D%0A         
+   
 return table
@@ -1451,13 +1451,22 @@
 n%5D;%0A    
+    %7D%0A    
 %7D
-%0A
 %0A%7D%0A

refactor 72