summaryrefslogtreecommitdiff log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
author committer Haidong Ji 2018-12-21 21:24:14 -0600 Haidong Ji 2018-12-21 21:24:14 -0600 4c1b19574b95e9db2c65f72b94bc55a86e4d6687 (patch) 229870614227fc36ccb76f87028172cfa0b86b95 f76bab93b3b58df4510a480d28e547125b5f3020 (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.javanew file mode 100644index 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] = i;+ }+ for (int j = 0; j < m + 1; j++) {+ D[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.javanew file mode 100644index 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"));+ }++}