added dynamic programming top down apprach for 72 with explanation (#134)

ashmichheda · web-flow · commit 315090be5ebb · 2020-11-14T09:57:56.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_72.java b/src/main/java/com/fishercoder/solutions/_72.java
@@ -1,5 +1,7 @@
 package com.fishercoder.solutions;
 
+import java.util.Arrays;
+
 public class _72 {
 
     public static class Solution1 {
@@ -35,4 +37,45 @@ public int minDistance(String word1, String word2) {
             return table[m][n];
         }
     }
+    public static class Solution2{
+        public int minDistance(String word1, String word2) {
+            // using levenshtein Distance to find minimum transformation operations required from word 1 to word 2
+            int[][] dp = new int[word1.length()][word2.length()];
+            // fill the dp array with -1 value
+            for(int [] rows : dp){
+                Arrays.fill(rows, -1);
+            }
+            return levenshteinDistance(word1, word1.length()-1 , word2, word2.length()-1, dp);
+        }
+        private int levenshteinDistance( String s1, int s1Index, String s2, int s2Index, int[][] dp){
+
+            if(s1Index < 0){ // when s1 is "" perform all insertions to get s1 to s2
+                return s2Index + 1;
+            }
+            else if(s2Index < 0) { // when s2 is "" perform all deletions from s1
+                return s1Index + 1;
+            }
+
+            // base condition when dp array is filled, return the distance
+            if(dp[s1Index][s2Index] != -1)
+                return dp[s1Index][s2Index];
+
+            if(s1.charAt(s1Index) == s2.charAt(s2Index)){
+                // Characters match, no edit distance to be calculated
+                dp[s1Index][s2Index] = levenshteinDistance(s1, s1Index - 1, s2, s2Index - 1, dp);
+            }
+            else{
+                // When there is a character mismatch, perform operations
+
+                // Insertion
+                int insertValue = levenshteinDistance(s1, s1Index, s2, s2Index - 1, dp);
+                int deleteValue = levenshteinDistance(s1, s1Index - 1, s2, s2Index, dp);
+                int substituteValue = levenshteinDistance(s1, s1Index - 1, s2, s2Index - 1, dp);
+
+                /* Now we need to take the minimum of the 3 operations to find the edit distance and add 1 to the min cost action denoting that an action is performed */
+                dp[s1Index][s2Index] = 1 + Math.min(insertValue, Math.min(deleteValue, substituteValue));
+            }
+            return dp[s1Index][s2Index];
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_72Test.java b/src/test/java/com/fishercoder/_72Test.java
@@ -8,14 +8,21 @@
 
 public class _72Test {
     private static _72.Solution1 solution1;
+    private static _72.Solution2 solution2;
+
 
     @BeforeClass
     public static void setup() {
-        solution1 = new _72.Solution1();
+        solution1 = new _72.Solution1(); solution2 = new _72.Solution2();
     }
 
     @Test
     public void test1() {
         assertEquals(1, solution1.minDistance("Ada", "Adam"));
     }
+
+    @Test
+    public void test2() {
+        assertEquals(5, solution1.minDistance("Ashmi", "Chheda"));
+    }
 }
