String Edit Distance done!

Implementing the algo described in lecture. Getting 2 dimensional array
indexing right took a bit of time. Looking at the picture helped me in
realizing that the dimention should have been n+1 by m+1. First time
dealing with string edit distance and alignment game, pretty
interesting!

2 files changed, 65 insertions, 0 deletions

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java b/AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java
new file mode 100644
index 0000000..640d6e3
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java
@@ -0,0 +1,43 @@
+import java.util.Scanner;
+
+public class EditDistance {
+
+    public static void main(String args[]) {
+        Scanner scan = new Scanner(System.in);
+
+        String s = scan.next();
+        String t = scan.next();
+
+        System.out.println(editDistance(s, t));
+      }
+
+    public static int editDistance(String A, String B) {
+        int m = B.length();
+        int n = A.length();
+        int[][] D = new int[n + 1][m + 1];
+
+        for (int i = 0; i < n + 1; i++) {
+            D[i][0] = i;
+        }
+        for (int j = 0; j < m + 1; j++) {
+            D[0][j] = j;
+        }
+
+        for (int j = 1; j < m + 1; j++) {
+            for (int i = 1; i < n + 1; i++) {
+                int insertion = D[i][j - 1] + 1;
+                int deletion = D[i - 1][j] + 1;
+                int match = D[i - 1][j - 1];
+                int mismatch = D[i - 1][j - 1] + 1;
+                if (A.toCharArray()[i - 1] == B.toCharArray()[j - 1]) {
+                    D[i][j] = Math.min(insertion, Math.min(deletion, match));
+                } else {
+                    D[i][j] = Math.min(insertion, Math.min(deletion, mismatch));
+                }
+            }
+        }
+
+        return D[n][m];
+    }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java b/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java
new file mode 100644
index 0000000..8c10432
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java
@@ -0,0 +1,22 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class EditDistanceTest {
+
+    @Test
+    void test() {
+        assertEquals(0, EditDistance.editDistance("ab", "ab"));
+    }
+
+    @Test
+    void test1() {
+        assertEquals(3, EditDistance.editDistance("short", "ports"));
+    }
+
+    @Test
+    void test2() {
+        assertEquals(5, EditDistance.editDistance("editing", "distance"));
+    }
+
+}