1143.最长公共子序列 (Medium)*

题目描述*

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。

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

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

示例*

输入：text1 = "abcde", text2 = "ace"

输出：3

解释：最长公共子序列是 "ace"，它的长度为 3。

输入：text1 = "abc", text2 = "abc"

输出：3

解释：最长公共子序列是 "abc"，它的长度为 3。

提示*

1 <= text1.length <= 1000, 1 <= text2.length <= 1000

输入的字符串只含有小写英文字符。

代码*

最长公共子序列 Longest Common Subsequense，是典型的二维动态规划问题。因为动态规划算法做的就是穷举和剪枝。

两个字符串的动态规划问题，需要构造二维 dp 数组，dp[i][j] 的含义是对于 s1[1...i] 和 s2[1...j]（我们先假设索引是从 1 开始），他们的 LCS 为 dp[i][j]。

初始状态下，dp[0][..] 和 dp[..][0] 应该初始化为 0，即任何字符串与空串的 LCS 为零。

状态转移方程，开始比较难想，不过字符串类问题大致差不多。状态转移就是做选择，对于两个字符串中的字符，要么在 lcs 中，要么不在。在 lcs 中的字符必定同时在两个字符串中，可以用两个指针同时遍历两个字符串，如果 s1[i] == s2[j]，那么这个字符一定在 lcs 中，否则这两个字符至少有一个不在 lcs 中。以下是递归伪代码：

def longestCommonSubsequence(str1, str2) -> int:
    def dp(i, j):
        if i == -1 or j == -1:
            return 0
        if str1[i] == str2[j]:
            return dp(i - 1, j - 1) + 1
        else :
            return max(dp(i - 1, j), dp(i, j - 1))

    return dp(len(str1) - 1, len(str2) - 1)

如果找到 lcs 的字符，指针前移，长度加 1，否则要把两个指针分别向前，取较大者。我们可以通过 dp 数组优化之间复杂度。对应的状态转移方程应为：

dp[i][j] = (str1[i - 1] == str2[j - 1]) ? (1 + dp[i - 1][j - 1]) : max(dp[i - 1][j], dp[i][j - 1])

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        for(int i = 1; i <= text1.size(); i++) {
            for(int j = 1; j <= text2.size(); j++) {
                if(text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                }else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};