From c4ef43d3e77450b45bb7fb988bff0923ef8276fe Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 23 Dec 2018 16:02:16 -0600
Subject: Longest Common Subsequence of two sequences not done

I do want to record this because the algos were written based on lecture
slides, and it passed all my own tests. However, it didn't pass test 14
of 37 from course grader. I checked forums in both edX and Coursera, I
was not alone in having that issue, but neither forums provided the
answer to the 14th test case used by the grader.---
 AlgoDesignAndTechniqueEdxJava/sources/LCS2.java    | 69 ++++++++++++++++++++++
 .../tests/EditDistanceTest.java                    |  1 +
 AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java  | 35 +++++++++++
 3 files changed, 105 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
 create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
new file mode 100644
index 0000000..d214eff
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
@@ -0,0 +1,69 @@
+import java.util.Scanner;
+
+public class LCS2 {
+
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        int n = scanner.nextInt();
+        int[] a = new int[n];
+        for (int i = 0; i < n; i++) {
+            a[i] = scanner.nextInt();
+        }
+
+        int m = scanner.nextInt();
+        int[] b = new int[m];
+        for (int i = 0; i < m; i++) {
+            b[i] = scanner.nextInt();
+        }
+
+        System.out.println(lcs2(a, b));
+    }
+
+    public static int[][] editDistance(int[] A, int[] 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[i - 1] == B[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;
+    }
+
+    public static int lcs2(int[] a, int[] b) {
+        int D[][] = editDistance(a, b);
+        return lcs2(a.length, b.length, D);
+    }
+
+    private static int lcs2(int i, int j, int[][] D) {
+        if (i == 0 && j == 0)
+            return 0;
+        if (i > 0 && D[i][j] == D[i - 1][j] + 1)
+            return lcs2(i - 1, j, D);
+        if (j > 0 && D[i][j] == D[i][j - 1] + 1)
+            return lcs2(i, j - 1, D);
+        else if (D[i][j] == D[i - 1][j - 1])
+            return 1 + lcs2(i - 1, j - 1, D);
+        else
+            return lcs2(i - 1, j - 1, D);
+    }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java b/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java
index 8c10432..e22ed87 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java
@@ -7,6 +7,7 @@ class EditDistanceTest {
     @Test
     void test() {
         assertEquals(0, EditDistance.editDistance("ab", "ab"));
+        assertEquals(1, EditDistance.editDistance("a", "x"));
     }
 
     @Test
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
new file mode 100644
index 0000000..bdfa799
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
@@ -0,0 +1,35 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class LCS2Test {
+
+    @Test
+    void test() {
+        int[] a = {2, 7, 5};
+        int[] b = {2, 5};
+        assertEquals(2, LCS2.lcs2(a,b));
+    }
+
+    @Test
+    void test1() {
+        int[] a = {7};
+        int[] b = {1, 2, 3, 4};
+        assertEquals(0, LCS2.lcs2(a,b));
+    }
+
+    @Test
+    void test2() {
+        int[] a = {2, 7, 8, 3};
+        int[] b = {5, 2, 8, 7};
+        assertEquals(2, LCS2.lcs2(a,b));
+    }
+
+    @Test
+    void test3() {
+        int[] a = {1, 2, 3, 4, 5, 6, 7};
+        int[] b = {1, 2, 8, 4, 5, 6};
+        assertEquals(5, LCS2.lcs2(a,b));
+    }
+
+}
-- 
cgit v1.2.3