LintCode 77. Longest Common Subsequence

Algorithm

• Two input string a with length lengthA and b with length lengthB
• lookup[i][j] is defined as length of LCS of substring of a with index from 0 to i - 1 and substring of b with index from 0 to j - 1.
• if a[i - 1] == b[j - 1], then lookup[i][j] = lookup[i - 1][j - 1]
• otherwise, lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1])
• At last, lookup[lengthA][lengthB] is the LCS.

Code

public class LCS {
    private int[][] lookupRecursive;
    public int longestCommonSubsequenceRecursive(String A, String B) {
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        lookupRecursive = new int[a.length + 1][b.length + 1];
        for (int i = 0; i <= a.length; i++) {
            for (int j = 0; j <= b.length; j++) {
                lookupRecursive[i][j] = -1;
            }
        }
        int length = lcs(a, b, a.length, b.length);
        printLCS(lookupRecursive, a, b);
        return length;
    }

    private int lcs(char[] a, char[] b, int endA, int endB) {
        if (endA == 0 || endB == 0) {
            lookupRecursive[endA][endB] = 0;
        } else if (a[endA - 1] == b[endB - 1]) {
            if (lookupRecursive[endA][endB] == -1) {
                lookupRecursive[endA][endB] = lcs(a, b, endA - 1, endB - 1) + 1;
            }
        } else {
            if (lookupRecursive[endA][endB] == -1) {
                lookupRecursive[endA][endB] = Math.max(lcs(a, b, endA - 1, endB), lcs(a, b, endA, endB - 1));
            }
        }
        return lookupRecursive[endA][endB];
    }

    public int longestCommonSubsequenceIterative(String A, String B) {
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        int[][] lookupIterative = new int[a.length + 1][b.length + 1];
        for (int i = 1; i <= a.length; i++) {
            for (int j = 1; j <= b.length; j++) {
                if (a[i - 1] == b[j - 1]) {
                    lookupIterative[i][j] = lookupIterative[i - 1][j - 1] + 1;
                } else {
                    lookupIterative[i][j] = Math.max(lookupIterative[i - 1][j], lookupIterative[i][j - 1]);
                }
            }
        }
        printLCS(lookupIterative, a, b);
        return lookupIterative[a.length][b.length];
    }

    private void printLCS(int[][] lookup, char[] a, char[] b) {
        int size = lookup[a.length][b.length];
        char[] lcs = new char[size];
        int lastIndex = size - 1;
        int i = a.length, j = b.length;
        while (lastIndex >= 0) {
            if (a[i - 1] == b[j - 1]) {
                lcs[lastIndex] = a[i - 1];
                lastIndex--;
                i--;
                j--;
            } else if (lookup[i - 1][j] > lookup[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        System.out.println(String.valueOf(lcs));
    }

    public static void main(String[] args) {
        String X = "AGGTAB";
        String Y = "GXTXAYB";
        System.out.println(new LCS().longestCommonSubsequenceIterative(X, Y));
        System.out.println(new LCS().longestCommonSubsequenceRecursive(X, Y));
    }
}

Print the LCS

• Create an a character array with length equal to the length of LCS to store LCS string.
• Traverse the 2D array from right and bottom most corner and store characters in above array
• if current characters in a and b are same, it is part of LCS.
• otherwise, compare lookup[i - 1][j] and lookup[i][j - 1], and go in direction of larger value.

private void printLCS(int[][] lookup, char[] a, char[] b) {
    int size = lookup[a.length][b.length];
    char[] lcs = new char[size];
    int lastIndex = size - 1;
    int i = a.length, j = b.length;
    while (lastIndex >= 0) {
        if (a[i - 1] == b[j - 1]) {
            lcs[lastIndex] = a[i - 1];
            lastIndex--;
            i--;
            j--;
        } else if (lookup[i - 1][j] > lookup[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    System.out.println(String.valueOf(lcs));
}