1143. 最长公共子序列
一句话套路相等取对角+1,不等取 max(上,左)
题目描述
给定两个字符串 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 <= 1000text1和text2仅由小写英文字符组成。
思路
时间
O(mn)空间
O(mn)(求长度可滚动成 O(n),但要输出方案就得留整表)状态
dp[i][j] = text1 前 i 个 与 text2 前 j 个 的 LCS 长度。
转移
相等 -> dp[i-1][j-1] + 1(这个字符必进 LCS);
不等 -> max(dp[i-1][j], dp[i][j-1])(各退一步)。
「子序列 vs 子串」:子串必须连续,状态要改成「以 i/j 结尾」并取 max(Q718);
子序列可以不连续,所以 dp[i][j] 直接是答案。
输出方案
从 (m,n) 反向走,遇到「相等且来自对角线」就记录该字符。
图解
字符串
shmtulqrypy(来自本仓库测试数据,下标从 0 开始)逐帧动画
1 / 2
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc01143 {
class Solution {
public:
int longestCommonSubsequence(const string& a, const string& b) {
const int m = (int)a.size(), n = (int)b.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)
dp[i][j] = (a[i - 1] == b[j - 1]) ? dp[i - 1][j - 1] + 1
: max(dp[i - 1][j], dp[i][j - 1]);
return dp[m][n];
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc01143::Solution s;
CHECK_EQ(s.longestCommonSubsequence("abcde", "ace"), 3);
CHECK_EQ(s.longestCommonSubsequence("abc", "abc"), 3);
CHECK_EQ(s.longestCommonSubsequence("abc", "def"), 0);
CHECK_EQ(s.longestCommonSubsequence("bsbininm", "jmjkbkjkv"), 1);
CHECK_EQ(s.longestCommonSubsequence("", "a"), 0);
CHECK_EQ(s.longestCommonSubsequence("oxcpqrsvwf", "shmtulqrypy"), 2);