Longest Common Subsequence

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

Notes:

1. Double sequence DP
2. State: f[i][j] the biggest length for string(0..i) and string(0..j)
3. Function:
   1. f[i][j] = Max(f[i][j], f[i-1][j-1]+1) when A[i] == B[j]
   2. f[i][j] = Max(f[i-1][j], f[i][j-1]) when A[i] != B[j]
4. Initialize: f[0][i] = 0, f[i][0] = 0
5. Answer: f[m][n]

    public int longestCommonSubsequence(String A, String B) {
        if (A == null || A.isEmpty() || B == null || B.isEmpty()) {
            return 0;
        }

        int m = A.length();
        int n = B.length();

        // state
        int[][] f = new int[m+1][n+1];

        // initialize, could skip
        for (int i = 0; i <= m; ++i) {
            f[i][0] = 0;
        }

        for (int i = 0; i <= n; ++i) {
            f[0][i] = 0;
        }

        // function
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (A.charAt(i-1) == B.charAt(j-1)) {
                    f[i][j] = Math.max(f[i][j], f[i-1][j-1]+1);
                } else {
                    f[i][j] = Math.max(f[i-1][j-1], Math.max(f[i-1][j], f[i][j-1]));
                }
            }
        }

        // answer
        return f[m][n];
    }