LeetCode - Algorithms - 1143. Longest Common Subsequence

Problem

1143. Longest Common Subsequence

The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.

For the general case of an arbitrary number of input sequences, the problem is NP-hard. When the number of sequences is constant, the problem is solvable in polynomial time by dynamic programming.

The LCS problem has an optimal substructure: the problem can be broken down into smaller, simpler subproblems, which can in turn be broken down into simpler subproblems, and so on, until, finally, the solution becomes trivial. LCS in particular has overlapping subproblems: the solutions to high-level subproblems often reuse solutions to lower level subproblems. Problems with these two properties are amenable to dynamic programming approaches, in which subproblem solutions are memoized, that is, the solutions of subproblems are saved for reuse.

Java

Hunt–Szymanski algorithm

Translation of © Hunt-Szymanski Algorithm(Match-List, 1977)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        final int LEN1 = text1.length(), LEN2 = text2.length();
        return huntSzymanski_lcs(text1.toCharArray(), text2.toCharArray(), LEN1, LEN2);    
    }
    
    private int huntSzymanski_lcs(char[] stringA, char[] stringB, int m, int n) {
        final int alphabet_size = 256;
        int i, j, k, LCS, high, low, mid;
        int[][] matchlist = new int[alphabet_size][];
        int[] L;
        for (i = 0; i < alphabet_size; i++) {
            matchlist[i] = new int[n + 2];
        }
        L = new int[n + 1];

        // make the matchlist
        for (i = 0; i < m; i++) {
            if (matchlist[stringA[i]][0] == 0) {
                matchlist[stringA[i]][0] = 0;

                for (k = 1, j = n - 1; j >= 0; j--) {
                    if (stringA[i] == stringB[j]) {
                        matchlist[stringA[i]][k] = j + 1;
                        k++;
                    }
                    matchlist[stringA[i]][k] = -1;
                }
            }
        }

        // finding the LCS
        for (LCS = 0, i = 0; i < m; i++) {
            for (j = 0; matchlist[stringA[i]][j] != -1; j++) {
                // if the number bigger then the biggest number in the L, LCS + 1
                if (matchlist[stringA[i]][j] > L[LCS]) {
                    LCS++;
                    L[LCS] = matchlist[stringA[i]][j];
                }
                // else, do the binary search to find the place to insert the number
                else {
                    high = LCS;
                    low = 0;
                    k = 0;
                    while (true) {
                        mid = low + ((high - low) / 2);
                        if (L[mid] == matchlist[stringA[i]][j]) {
                            k = 1;
                            break;
                        }
                        if (high - low <= 1) {
                            mid = high;
                            break;
                        }
                        if (L[mid] > matchlist[stringA[i]][j]) {
                            high = mid;
                        } else if (L[mid] < matchlist[stringA[i]][j]) {
                            low = mid;
                        }
                    }
                    if (k == 0) {
                        L[mid] = matchlist[stringA[i]][j];
                    }
                }
            }
        }
        return LCS;
    }    
}

Submission Detail

  • 43 / 43 test cases passed.
  • Runtime: 12 ms, faster than 32.13% of Java online submissions for Longest Common Subsequence.
  • Memory Usage: 39.2 MB, less than 92.10% of Java online submissions for Longest Common Subsequence.

Dynamic Programming

bottom-up approach

Oftentimes I found Wikipedia is helpful when doing leetcode algorithm problems.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        final int LEN1 = text1.length(), LEN2 = text2.length();
        int[][] C = new int[LEN1 + 1][LEN2 + 1];
        for (int i = 1; i <= LEN1; i++) {
            for (int j = 1; j <= LEN2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    C[i][j] = C[i - 1][j - 1] + 1;
                } else {
                    C[i][j] = C[i - 1][j] > C[i][j - 1] ? C[i - 1][j] : C[i][j - 1];
                }
            }
        }
        return C[LEN1][LEN2];     
    }
}

Submission Detail

  • 43 / 43 test cases passed.
  • Runtime: 18 ms, faster than 17.54% of Java online submissions for Longest Common Subsequence.
  • Memory Usage: 42.8 MB, less than 51.59% of Java online submissions for Longest Common Subsequence.

top-down approach (momoized version)

© https://www.techiedelight.com/longest-common-subsequence/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        final int LEN1 = text1.length(), LEN2 = text2.length();
        Map<String, Integer> map = new HashMap<String, Integer>();
        return lcsLength(text1, text2, LEN1, LEN2, map);
    }
    
    private int lcsLength(String X, String Y, int m, int n, Map<String, Integer> lookup) {
        // return if we have reached the end of either string
        if (m == 0 || n == 0)
            return 0;

        // construct an unique map key from dynamic elements of the input
        String key = m + "|" + n;

        // if sub-problem is seen for the first time, solve it and
        // store its result in a map
        if (!lookup.containsKey(key)) {
            // if last character of X and Y matches
            if (X.charAt(m - 1) == Y.charAt(n - 1)) {
                lookup.put(key, lcsLength(X, Y, m - 1, n - 1, lookup) + 1);

            } else {
                // else if last character of X and Y don't match
                lookup.put(key, Integer.max(lcsLength(X, Y, m, n - 1, lookup), lcsLength(X, Y, m - 1, n, lookup)));
            }
        }

        // return the subproblem solution from the map
        return lookup.get(key);
    }   
}

Submission Detail

  • 43 / 43 test cases passed.
  • Runtime: 295 ms, faster than 5.04% of Java online submissions for Longest Common Subsequence.
  • Memory Usage: 167 MB, less than 5.04% of Java online submissions for Longest Common Subsequence.

javascript

Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    var LEN1 = text1.length, LEN2 = text2.length;
    var C = [];
    for (var i = 0; i <= LEN1; i++) {
        C.push([]);
        for (var j = 0; j <= LEN2; j++) {
            C[i].push(0);
        }
    }
    for (var i = 1; i <= LEN1; i++) {
        for (var j = 1; j <= LEN2; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                C[i][j] = C[i - 1][j - 1] + 1;
            } else {
                C[i][j] = C[i - 1][j] > C[i][j - 1] ? C[i - 1][j] : C[i][j - 1];
            }
        }
    }
    return C[LEN1][LEN2];    
};

Submission Detail

  • 43 / 43 test cases passed.
  • Runtime: 116 ms, faster than 60.08% of JavaScript online submissions for Longest Common Subsequence.
  • Memory Usage: 53.4 MB, less than 22.63% of JavaScript online submissions for Longest Common Subsequence.