HHot 100C++ 图解

1143. 最长公共子序列

中等 多维动态规划 2 帧动画 在力扣上做

一句话套路相等取对角+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 <= 1000
  • text1 和 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) 反向走,遇到「相等且来自对角线」就记录该字符。

图解

s 0 h 1 m 2 t 3 u 4 l 5 q 6 r 7 y 8 p 9 y 10
字符串 shmtulqrypy(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 2

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/16_dp_multidim.cpp14 行
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];
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q1143_lcs7 行
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);

↑↓ 选择↵ 打开/ 随时唤起