[LeetCode] 问题系列 - LCS: Longest C

经典问题：LCS（最长公共字符长度）

问题
给两个string A B，找这两个string里面的LCS: 最长公共字符长度 (不需要是continuous substring)

例子
如果两个string是"abcde"和"zdcazyx"，LCS 是 "a" (or d or c)，返回1；
如果两个string是"abcd"和"eacb"，LCS 是"ac"，返回2。

思路
dp[i][j]: longest common subsequence length for items: A[0 ~ i - 1] and B[0 ~ j - 1]

Conditions:

• A[i - 1] != B[j - 1]: no action
• A[i - 1] == B[j - 1]: 可以更新dp方程dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1)

代码

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        if (A == null || B == null || A.length() == 0 || B.length() == 0) {
            return 0;
        }
        int[][] dp = 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.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], dp[i - 1][j]);
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
                }
            }
        }
        return dp[A.length()][B.length()];
    }
}

衍生题目

72. Edit Distance
583. Delete Operation for Two Strings
1035. Uncrossed Lines