BAEL 1143 - Edit Distance - deep20jain@gmail.com (eugenp#2718)

deep20jain · pivovarit · commit 5d39af398fbf · 2017-10-24T05:36:28.000+02:00
* Calculate edit distance

* Fixing formatting

* Making variable local to method
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/editdistance/EditDistanceBase.java b/algorithms/src/main/java/com/baeldung/algorithms/editdistance/EditDistanceBase.java
@@ -0,0 +1,22 @@
+package com.baeldung.algorithms.editdistance;
+
+public class EditDistanceBase {
+
+    public static int costOfSubstitution(char a, char b) {
+        if (a == b) {
+            return 0;
+        }
+        return 1;
+    }
+
+    public static int min(int... numbers) {
+        int min = Integer.MAX_VALUE;
+
+        for (int x : numbers) {
+            if (x < min)
+                min = x;
+        }
+
+        return min;
+    }
+}
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/editdistance/EditDistanceDynamicProgramming.java b/algorithms/src/main/java/com/baeldung/algorithms/editdistance/EditDistanceDynamicProgramming.java
@@ -0,0 +1,25 @@
+package com.baeldung.algorithms.editdistance;
+
+public class EditDistanceDynamicProgramming extends EditDistanceBase {
+
+    public static int calculate(String x, String y) {
+        int[][] dp = new int[x.length() + 1][y.length() + 1];
+
+        for (int i = 0; i <= x.length(); i++) {
+            for (int j = 0; j <= y.length(); j++) {
+                if (i == 0)
+                    dp[i][j] = j;
+
+                else if (j == 0)
+                    dp[i][j] = i;
+
+                else {
+                    dp[i][j] = min(dp[i - 1][j - 1] + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), dp[i - 1][j] + 1, dp[i][j - 1] + 1);
+                }
+            }
+        }
+
+        return dp[x.length()][y.length()];
+    }
+
+}
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/editdistance/EditDistanceRecursive.java b/algorithms/src/main/java/com/baeldung/algorithms/editdistance/EditDistanceRecursive.java
@@ -0,0 +1,20 @@
+package com.baeldung.algorithms.editdistance;
+
+public class EditDistanceRecursive extends EditDistanceBase {
+
+    public static int calculate(String x, String y) {
+
+        if (x.isEmpty())
+            return y.length();
+
+        if (y.isEmpty())
+            return x.length();
+
+        int substitution = calculate(x.substring(1), y.substring(1)) + costOfSubstitution(x.charAt(0), y.charAt(0));
+        int insertion = calculate(x, y.substring(1)) + 1;
+        int deletion = calculate(x.substring(1), y) + 1;
+
+        return min(substitution, insertion, deletion);
+    }
+
+}
diff --git a/algorithms/src/test/java/com/baeldung/algorithms/editdistance/EditDistanceDataProvider.java b/algorithms/src/test/java/com/baeldung/algorithms/editdistance/EditDistanceDataProvider.java
@@ -0,0 +1,21 @@
+package com.baeldung.algorithms.editdistance;
+
+import org.junit.runners.Parameterized.Parameters;
+
+import java.util.Arrays;
+import java.util.Collection;
+
+public class EditDistanceDataProvider {
+
+    @Parameters
+    public static Collection<Object[]> getLists() {
+        return Arrays.asList(new Object[][] { 
+            { "", "", 0 }, 
+            { "ago", "", 3 }, 
+            { "", "do", 2 }, 
+            { "abc", "adc", 1 }, 
+            { "peek", "pesek", 1 }, 
+            { "sunday", "saturday", 3 } 
+        });
+    }
+}
diff --git a/algorithms/src/test/java/com/baeldung/algorithms/editdistance/EditDistanceTest.java b/algorithms/src/test/java/com/baeldung/algorithms/editdistance/EditDistanceTest.java
@@ -0,0 +1,31 @@
+package com.baeldung.algorithms.editdistance;
+
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class EditDistanceTest extends EditDistanceDataProvider {
+
+    String x;
+    String y;
+    int result;
+
+    public EditDistanceTest(String a, String b, int res) {
+        super();
+        x = a;
+        y = b;
+        result = res;
+    }
+
+    @Test
+    public void testEditDistance_RecursiveImplementation() {
+        Assert.assertEquals(result, EditDistanceRecursive.calculate(x, y));
+    }
+
+    @Test
+    public void testEditDistance_givenDynamicProgrammingImplementation() {
+        Assert.assertEquals(result, EditDistanceDynamicProgramming.calculate(x, y));
+    }
+}
