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.

1 files changed, 69 insertions, 0 deletions

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);
+    }
+
+}