Problem

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.

暴力解法:

• 时间复杂度
  • O(2 ^ (m + n))

思路:

• When comes to this problem, I am always thinking if I assume I got the subproblems solved, and I only left the final step to solve the whole problem, what's the relationship between subproblem and the original problem.
• Let's say,
  • I knew lcs for the first i characters of s1 and first j characters of s2
• • I already know lcs for the above strings' substring "ABC" and "EAC" , just left the final position of these two strings to determine.
• assume I have two index respectively representing the final index in two strings, i for s1, j for s2.
  • if s1(i) == s2(j),
    • lcs("ABCD")("EACB") = lcs("ABC")("EAC") + 1
  • else
    • lcs("ABCD")("EACB") = MAX {lcs("ABCB")("EAC"), lcs("ABC")("EACD")
• so our state is longest common subsequence
• so we need a two-dimensional array to store these state
• state:
  • dp[i][j]: the lcs for the first i characters of s1, and first j characters of s2
• function:
  • if s1(i) == s2(j)
    • dp[i][j] = dp[i - 1][j - 1] + 1
  • else
    • dp[i][j] = max { dp[i][j - 1], dp[i - 1][j] }
• initialize:
  • dp[0][0] = 0
• answer:
  • dp[m][n]

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

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

        int[][] dp = new int[m + 1][n + 1];

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

        return dp[m][n];
    }