LongestCommonSubsequence.java

/*
    Problem: Given two strings, find the longest common subsequence.

    Optimal substructure:
    LCS(X, Y, m, n) = LCS(X, Y, m-1, n-1) + 1                          if X[m-1] == Y[n-1]
                      MAX(LCS(X, Y, m-2, n-1), LCS(X, Y, m-1, n-2))    otherwise
 */
public class LongestCommonSubsequence {
    // complexity: time O(2^n), space O(n)
    static int findLCSRecur(String X, String Y, int m, int n) {
        // base case
        if (m == 0 || n == 0) {
            return 0;
        }
        if (X.charAt(m-1) == Y.charAt(n-1)) {
            return findLCSRecur(X, Y, m-1, n-1) + 1;
        } else {
            return Math.max(findLCSRecur(X, Y, m, n-1), findLCSRecur(X, Y, m-1, n));
        }
    }

    // complexity: time O(n*m), space O(n*m)
    static int findLCS(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] memo = new int[m + 1][n + 1];
        // initialize
        for (int i = 0; i <= m; i++) {
            memo[i][0] = 0;
        }
        for (int i = 0; i <= n; i++) {
            memo[0][i] = 0;
        }
        // fill the rest
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X.charAt(i-1) == Y.charAt(j-1)) {
                    memo[i][j] = memo[i-1][j-1] + 1;
                } else {
                    memo[i][j] = Math.max(memo[i-1][j], memo[i][j-1]);
                }
            }
        }
        return memo[m][n];
    }

    public static void main(String[] args) {
        String X = "ACBDEA";
        String Y = "ABCDA";
        System.out.println(findLCSRecur(X, Y, X.length(), Y.length()));
        System.out.println(findLCS(X, Y));
        X = "AGGTAB";
        Y = "GXTXAYB";
        System.out.println(findLCSRecur(X, Y, X.length(), Y.length()));
        System.out.println(findLCS(X, Y));
    }
}

/*
References:
http://algorithms.tutorialhorizon.com/dynamic-programming-longest-common-subsequence/
http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
http://www.programcreek.com/2014/04/longest-common-subsequence-java/
*/