summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-21 21:24:14 -0600
committerHaidong Ji2018-12-21 21:24:14 -0600
commit4c1b19574b95e9db2c65f72b94bc55a86e4d6687 (patch)
tree229870614227fc36ccb76f87028172cfa0b86b95
parentf76bab93b3b58df4510a480d28e547125b5f3020 (diff)
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!
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java43
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java22
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"));
+ }
+
+}