LeetCode 1143. 最长公共子序列

◎

本节目标

比较两个字符串前缀的最后字符，构造二维公共子序列状态。

这是序列与字符串动态规划中双前缀匹配的母题。

题意与约束

求两个字符串的最长公共子序列长度；选出的字符顺序要保持，但可以不连续。

第一反应与重复子问题

比较两个前缀的最后字符：相同就能共同选取，不同就至少有一个最后字符不能出现在同一最优答案中。

状态定义与转移推导

令 dp[i][j] 为前 i 个和前 j 个字符的答案。字符相同则为 dp[i-1][j-1]+1；否则取 dp[i-1][j] 与 dp[i][j-1] 的较大值。

正确性依据

相同末尾可共同加入任一最优更短前缀；不同末尾的公共子序列必忽略其中至少一个末尾字符，两个分支已完全覆盖。

样例执行过程

abcde 与 ace 的匹配格沿对角线得到 a,c,e，长度为 3。

代码实现

C++

C++17

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

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

Python

Python 3

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        for first in range(1, len(text1) + 1):
            for second in range(1, len(text2) + 1):
                if text1[first - 1] == text2[second - 1]:
                    dp[first][second] = dp[first - 1][second - 1] + 1
                else:
                    dp[first][second] = max(dp[first - 1][second], dp[first][second - 1])
        return dp[-1][-1]

复杂度分析

设长度为 m,n，时间和二维状态空间均为 O(mn)。

边界与易错点

• 字符不同不代表结果为零，应保留一个前缀继续比较。
• 子序列不连续，不能改用最长公共子串的转移。

模式迁移

编辑距离、最长重复子序列和字符串对齐都从两个前缀的二维状态出发。