Sunday面试指南

最长公共子序列怎么求?为什么它和最长公共子串不是同一道题?

下面是一段模拟面试对话。

🧑‍💻 面试官: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 的独立解析。

浏览公司面试真题 →
简历汪永久免费在线制作简历,模板直接套用、导出无水印,永久免费、下载免费,不需要付费解锁任何功能。去写简历