最长公共子序列怎么求?为什么它和最长公共子串不是同一道题?
下面是一段模拟面试对话。
🧑💻 面试官:abc 和 ac 的最长公共子序列是什么?
🙋♂️ 我:是 ac,长度为 2,可以用动态规划求。
🧑💻 面试官:如果我把题目改成最长公共子串呢?
🙋♂️ 我:应该也是同样的转移,把相等的字符接上……
🧑💻 面试官:可 a 和 c 在第一个字符串里并不连续。这时你保存的状态,还能继续沿用吗?
先确认能不能跳过字符。子序列保留相对顺序,子串还要求连续;这个条件会直接改变状态的含义。
面试速答(60 秒版)
最长公共子序列允许跳过字符,只要求选出的字符在两个字符串中都保持原来的顺序。
我会用 dp[i][j] 表示两个字符串前 i 个、前 j 个字符的最长公共子序列长度。当前字符相同,就在两个更短前缀的答案上加一;不同,就分别尝试跳过其中一个字符,取较大的答案。
空字符串的答案是零,所以表格多留一行和一列。时间复杂度是 O(mn),二维表的空间复杂度也是 O(mn)。如果只求长度,可以进一步压缩空间。
最长公共子串则要求连续。通常把状态定义成“必须以当前位置结尾的公共连续片段长度”,字符不同时要归零,最后取整张表的最大值,不能直接套用子序列的转移。

知识点详解:允许跳过字符,怎样体现在状态里?
先把“顺序不变”理解清楚
比如 abcde 和 ace,可以从第一个字符串跳过 b、d,留下 ace。留下来的字符没有调换位置,因此它是公共子序列。
如果把它写成 eca 就不行了。子序列允许删除字符,不允许重新排列字符。
这也是为什么把两个字符串先排序,再求相同字符数量会答错。排序已经破坏了原题要求保留的顺序。原题约束见 LeetCode 1143。
一格表格,代表两个前缀的完整答案
咱们先不考虑“最后选中了哪个字符”,直接问一个更小的问题。
第一个字符串只看前 i 个字符,第二个只看前 j 个字符,这两个前缀最多能选出多长的公共子序列?把答案放进 dp[i][j]。
这样一来,dp[0][j] 和 dp[i][0] 都是零。任意一边没有字符,就选不出公共内容。表格的尺寸因此是 (m+1) × (n+1),不是 m × n。
接下来比较的是 a[i-1] 与 b[j-1]。这里的减一,是因为 i、j 表示长度,数组下标从零开始。
字符相同,接上;字符不同,考虑跳过谁
当两个末尾字符相同时,可以在更短前缀的公共子序列末尾接上这个字符。
dp[i][j] = dp[i-1][j-1] + 1
当它们不相同时,至少有一个末尾字符不参与当前答案。于是分别考虑跳过 a 的末尾,或者跳过 b 的末尾。
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
不要在不同的时候直接写成左上角。左上角相当于同时跳过两个字符,有可能把本来还能用的字符也丢掉。
用 abc 和 ac 看最后一个格子。末尾 c 相同,就去取 ab 和 a 的答案 1,再接上 c,得到 2。中间的 b 正是通过前面的“跳过”保留了这条选择。

TypeScript 与 Python 实现
下面按原题的小写英文字母范围实现,不涉及 Unicode 字素切分。二维数组每一行需要单独创建,不能让所有行共享同一个数组。
TypeScript
function longestCommonSubsequence(a: string, b: string): number {
const dp = Array.from({ length: a.length + 1 }, () =>
Array<number>(b.length + 1).fill(0));
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
dp[i][j] = a[i - 1] === b[j - 1]
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[a.length][b.length];
}
Python
def longest_common_subsequence(a: str, b: str) -> int:
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[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[len(a)][len(b)]
为什么子串遇到不同字符就要归零?
子串的常见状态是“以 a 的第 i 个字符和 b 的第 j 个字符结尾的公共连续片段长度”。注意,是必须在这里结尾。
当前字符相同,可以把左上角的连续片段延长一位。当前字符不同,连续片段就断了,这个格子只能是零,不能继承上方或左方。
对于 abc 和 ac,最长公共子序列是 ac,长度 2;最长公共子串只能选 a 或 c,长度 1。
子序列的完整答案在右下角。子串的最长片段可能早就结束了,所以需要记录所有格子的最大值。这两个差别比背公式更重要。
面试官继续追问

如果要输出具体的子序列呢?
保留二维表后,从右下角回溯。字符相同就收下这个字符并走向左上角;不同时,往保持较优答案的上方或左方走。最后把收集的字符反转。
相同长度可能对应多个合法答案。除非题目要求字典序最小,否则不要额外承诺唯一结果。
只求长度,空间怎么压缩?
每行只依赖上一行和本行左侧,可以保存两行,把空间降到 O(min(m,n))。进一步压成一行时,还要临时保存被覆盖前的左上角值,不能拿已经更新的值冒充上一行。
你会怎么验证?
先检查空字符串、完全相同、完全不同、重复字符和 abc/ac。短字符串还可以枚举子序列作为对照,检查动态规划是否错误地重复使用字符或打乱顺序。
面试速记卡
- 子序列允许跳过字符,但不能改变相对顺序。
dp[i][j]是两个前缀的完整答案,边界空前缀为零。- 字符相同取左上加一,不同取上方与左方的最大值。
- 子串要求连续,不同归零,答案取全表最大值。
- 二维实现时间、空间均为 O(mn);只求长度可以压缩空间。
公司面试真题
真题根据求职者公开面经整理,题意经过概括,非逐字原话或公司官方题库;本文为 Sunday 的独立解析。
百度 · 算法 · 日常实习
怎样求两个字符串的最长公共子序列?(题意整理)
21届腾讯百度等算法日常实习面经 · 百度部分 ↗
原帖发布于 2019-08-28;21 届是作者届次,面试日期未明确腾讯 · C++后端 · 校招(原帖标签)
怎样求最长公共子序列 LCS?(题意整理)
腾讯 C++后台开发面经 ↗
原帖编辑于 2019-11-30