最长公共子序列

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

如果不存在公共子序列，返回 0。

一个字符串的子序列是指：在不改变字符相对顺序的情况下，删除某些字符，也可以不删除任何字符后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的公共子序列，是这两个字符串共同拥有的子序列。

示例 1：

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

示例 2：

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

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成

解法一（二维动态规划）：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (text1[i - 1] == text2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
};

解法二（一维滚动数组优化）：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();

        vector<int> dp(n + 1, 0);

        for (int i = 1; i <= m; i++)
        {
            int prev = 0;

            for (int j = 1; j <= n; j++)
            {
                int temp = dp[j];

                if (text1[i - 1] == text2[j - 1])
                {
                    dp[j] = prev + 1;
                }
                else
                {
                    dp[j] = max(dp[j], dp[j - 1]);
                }

                prev = temp;
            }
        }

        return dp[n];
    }
};

核心思想

这题要求的是两个字符串的最长公共子序列长度。

子序列不要求连续，但必须保持原字符串中的相对顺序。

最直接的想法是枚举所有子序列，再判断它是否同时出现在两个字符串中。

但一个长度为 n 的字符串有大量子序列，直接枚举会超时。

这题最关键的观察是：

比较两个字符串的前缀时，答案只和更短前缀的答案有关。

所以可以用动态规划。

我们逐步考虑 text1 的前 i 个字符和 text2 的前 j 个字符。

如果两个前缀的最后一个字符相同，那么这个字符可以接在更短前缀的最长公共子序列后面。

如果最后一个字符不同，那么最长公共子序列不可能同时包含这两个最后字符，只能尝试舍弃其中一个。

状态定义

定义：

dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。

也就是：

text1[0...i - 1]
text2[0...j - 1]

这两个前缀之间的最长公共子序列长度。

题目要求的答案就是：

dp[m][n]

其中：

• m = text1.size()
• n = text2.size()

递推公式推导

考虑 dp[i][j]。

此时比较的是：

• text1 的第 i 个字符：text1[i - 1]
• text2 的第 j 个字符：text2[j - 1]

1. 两个字符相同

如果：

text1[i - 1] == text2[j - 1]

说明这个字符可以作为一个公共字符，接到前面两个更短前缀的最长公共子序列后面。

所以：

dp[i][j] = dp[i - 1][j - 1] + 1

代码中写成：

dp[i][j] = dp[i - 1][j - 1] + 1;

2. 两个字符不同

如果：

text1[i - 1] != text2[j - 1]

那么这两个最后字符不能匹配成同一个公共字符。

这时最长公共子序列只能来自两种情况中的较大者：

• 舍弃 text1[i - 1]，看 dp[i - 1][j]
• 舍弃 text2[j - 1]，看 dp[i][j - 1]

所以：

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

代码中写成：

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

边界情况

当其中一个前缀长度为 0 时，说明有一个字符串是空串。

空串和任何字符串的公共子序列长度都是 0。

所以：

dp[0][j] = 0
dp[i][0] = 0

代码中直接创建大小为 (m + 1) x (n + 1) 的数组，并初始化为 0：

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

这样就不需要单独处理第一行和第一列。

为什么可以按前缀长度递推

计算 dp[i][j] 时，只依赖三个已经更小的状态：

• dp[i - 1][j - 1]
• dp[i - 1][j]
• dp[i][j - 1]

如果按 i 从小到大、j 从小到大遍历：

• 上一行的状态已经算好
• 当前行左侧的状态也已经算好

所以每个状态都能由已知状态推出。

这就是动态规划的计算顺序。

解法二：一维滚动数组优化

二维动态规划中，计算当前行时，只需要用到：

• 上一行同一列的值：dp[i - 1][j]
• 当前行左一列的值：dp[i][j - 1]
• 上一行左上角的值：dp[i - 1][j - 1]

所以可以用一维数组 dp[j] 表示当前处理到这一行时，前 j 个字符对应的最长公共子序列长度。

更新时：

• 更新前的 dp[j] 表示二维里的 dp[i - 1][j]
• 更新后的 dp[j - 1] 表示二维里的 dp[i][j - 1]
• 变量 prev 保存二维里的 dp[i - 1][j - 1]

因此当两个字符相同：

dp[j] = prev + 1

当两个字符不同：

dp[j] = max(dp[j], dp[j - 1])

每次更新前先保存：

int temp = dp[j];

循环末尾再执行：

prev = temp;

这样下一列就能继续使用正确的左上角旧值。

正确性证明

我们证明：动态规划算法返回的结果等于两个字符串的最长公共子序列长度。

结论 1：边界初始化正确

当 i = 0 时，text1 的前缀是空串。

空串和 text2 的任意前缀都没有非空公共子序列，所以 dp[0][j] = 0。

当 j = 0 时，text2 的前缀是空串。

同理，dp[i][0] = 0。

因此边界初始化为 0 是正确的。

结论 2：当最后字符相同时，递推公式正确

如果 text1[i - 1] == text2[j - 1]，这个字符可以作为公共子序列的最后一个字符。

在它前面的部分，只能来自：

text1[0...i - 2]
text2[0...j - 2]

这两个更短前缀。

所以当前最长公共子序列长度是：

dp[i - 1][j - 1] + 1

这个转移不会破坏相对顺序，因为新增字符都在两个前缀的最后位置。

因此最后字符相同时的递推正确。

结论 3：当最后字符不同时，递推公式正确

如果 text1[i - 1] != text2[j - 1]，这两个字符不能匹配成同一个公共字符。

因此任意一个公共子序列，至少不会同时使用这两个最后字符。

如果不使用 text1[i - 1]，它的长度不会超过 dp[i - 1][j]。

如果不使用 text2[j - 1]，它的长度不会超过 dp[i][j - 1]。

取两者较大值，就覆盖了所有可能情况：

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

因此最后字符不同时的递推正确。

结论 4：计算顺序保证依赖状态已经完成

算法按前缀长度从小到大计算。

当计算 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j] 和 dp[i][j - 1] 都已经计算完成。

所以每个状态都能由正确的旧状态推出。

结论 5：一维滚动数组与二维动态规划等价

一维数组更新时，dp[j] 在更新前表示上一行同一列，更新后的 dp[j - 1] 表示当前行左一列，prev 表示上一行左上角。

这三个值正好对应二维递推所需的三个状态。

因此一维滚动数组只是复用了空间，不会改变计算结果。

得出结论

由结论 1 可知，边界初始化正确。

由结论 2 和结论 3 可知，状态转移正确。

由结论 4 可知，计算顺序正确。

由结论 5 可知，一维优化与二维动态规划等价。

因此算法返回的 dp[m][n] 或 dp[n] 就是两个字符串的最长公共子序列长度。

举例理解

以：

text1 = "abcde"
text2 = "ace"

为例。

字符匹配关系可以这样理解：

• text1[0] = 'a' 和 text2[0] = 'a' 匹配，公共子序列长度可以变成 1
• text1[2] = 'c' 和 text2[1] = 'c' 匹配，可以接在 "a" 后面，长度变成 2
• text1[4] = 'e' 和 text2[2] = 'e' 匹配，可以接在 "ac" 后面，长度变成 3

所以最长公共子序列是：

"ace"

长度是：

3

再看：

text1 = "abc"
text2 = "def"

两个字符串没有任何相同字符。

动态规划过程中不会出现字符相等的转移。

所以最终答案是：

0

复杂度分析

设 m = text1.length，n = text2.length。

解法一

需要计算 (m + 1) * (n + 1) 个状态。

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

解法二

同样需要计算每个状态一次。

一维数组长度为 n + 1。

• 时间复杂度：O(mn)
• 空间复杂度：O(n)

解法二空间更优，是更推荐的写法。