【每日算法Day 63】最长公共子序列

最长公共子序列（LCS）是一道经典的二维动态规划题目，许多子序列类型的问题会和穷举所有可能的结果相关，而动态规划做的就是穷举+剪枝，用来解决这类问题往往可以把指数级复杂度的子序列穷举降为次方级。

LeetCode 1143. 最长公共子序列 (opens new window)

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。1 <= text1.length <= 1000

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

解题思路

对于两个字符串的子串、子序列问题我们往往用一张二维表去描述问题的状态，本题中问题的状态是text1第一个字符到第i个字符的子串和text2第一个字符到第j个字符的子串的最长公共子序列长度。那么就用dp[i][j]表示该状态。边界case为dp[0][j]和dp[i][0]，表示空串与另一字符串的最长公共子序列长度，自然为0。

考虑dp[i][j]，如果text1第i个位置和text2第j个位置字符相同，则其长度为dp[i-1][j-1]+1；如果不相同，则这两个字符最多只有一个在最长子序列中，只需要比较dp[i - 1][j]和dp[i][j - 1]的最大值即可。（不用刻意考虑都不在的情况，例如text2的第j个字符不在，则dp[i-1][j-1]=dp[i-1][j]）这就是本问题的状态转移。

public int longestCommonSubsequence(String text1, String text2) {
    if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) return 0;
    int l1 = text1.length(), l2 = text2.length();
    int[][] dp = new int[l1 + 1][l2 + 1];
    for (int i = 1; i <= l1; i++) {
        for (int j = 1; j <= l2; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[l1][l2];
}