最长公共子序列问题中的字典序最小解
字数 4328 2025-12-23 14:58:52

最长公共子序列问题中的字典序最小解

题目描述
给定两个字符串 text1 和 text2，要求找出它们的最长公共子序列（Longest Common Subsequence, LCS）。但此题不仅要求长度，还需要输出 字典序最小 的 LCS。
若有多个 LCS 满足长度最长，则返回其中字典序最小的那个（按字符的 ASCII 码比较顺序）。

例如：

  • 输入：text1 = "abac", text2 = "cab"
    所有 LCS 为："ab"、"ac"、"cb"，长度均为 2；其中字典序最小的为 "ab"。
  • 输入：text1 = "abcde", text2 = "ace"
    唯一 LCS 为 "ace"，长度为 3。

第一步：回顾基础 LCS 长度的求法

经典 LCS 长度问题用动态规划：
定义 dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的 LCS 长度（i、j 从 1 开始）。
转移方程：

  • 若 text1[i-1] == text2[j-1]：
    dp[i][j] = dp[i-1][j-1] + 1
  • 否则：
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

边界：dp[0][j] = dp[i][0] = 0。

例如：text1 = "abac", text2 = "cab"，得到的 dp 矩阵如下（纵向 text1，横向 text2）：

c a b
0 0 0 0
a 0 0 1 1
b 0 0 1 2
a 0 0 1 2
c 0 1 1 2

LCS 长度为 dp[4][3] = 2。

第二步：引入字典序最小的 LCS 构造

我们需要在求长度的同时，记录所有能构成最长公共子序列的字符串中字典序最小的。

思路：

  1. 先按常规 DP 求出 LCS 长度。
  2. 然后反向追踪所有可能的 LCS 字符串，再选最小的。
    • 反向追踪时，若两字符相等，则该字符属于某个 LCS，加入结果，然后 i--, j--。
    • 若字符不等，则看 dp[i-1][j] 与 dp[i][j-1] 谁更大，往更大的方向走（保证还在最长序列的路径上）；如果两边一样大，则需要考虑哪条路径最终产生的字符串字典序更小。

难点：如果两边一样大（即向上或向左都可行），我们不能随便选一个方向，因为不同方向会导致最终得到的 LCS 字符串不同，可能字典序不一样。

关键观察：
假设我们现在在 (i, j)，text1[i-1] != text2[j-1]，且 dp[i-1][j] == dp[i][j-1]，那么：

  • 向上走 (i-1, j) 意味着忽略 text1[i-1]。
  • 向左走 (i, j-1) 意味着忽略 text2[j-1]。
    这两条路径最终得到的 LCS 字符串可能是不同的，我们需要选一个将来能得到 字典序最小 的 LCS 的方向。

如何比较？
可以这样想：我们从 (i, j) 开始，最终构造的 LCS 字符串是从后往前构建的（因为我们是反向追踪）。
字典序比较是从前向后比较，但是反向追踪时，我们得到的字符是逆序的（最后一个字符先得到）。
如果我们希望最终字符串字典序最小，那么在同样长度的情况下，应该尽早出现较小的字符。

但在反向过程中，我们无法预知前面会有什么字符，除非我们预先知道所有可能的 LCS 字符串——这需要搜索所有路径，成本较高。

第三步：另一种解法——同时递推 LCS 字符串

定义 dp[i][j] 为 (i, j) 状态对应的字典序最小的 LCS 字符串（而不只是长度）。这样递推时需要同时考虑长度优先，其次字典序。

递推方法：

  • 如果 text1[i-1] == text2[j-1]：
    新的 LCS = dp[i-1][j-1] + text1[i-1]。
  • 否则：
    候选1 = dp[i-1][j]
    候选2 = dp[i][j-1]
    先比较长度：选长度更大的；如果长度相等，选字典序更小的。

边界：dp[i][0] 和 dp[0][j] 都是空字符串 ""。

这样，dp[n][m] 就是答案。

例子演示：text1 = "abac", text2 = "cab"

初始化：
dp[0][*] = ""，dp[*][0] = ""

逐行计算（记录 dp[i][j] 字符串）：

  • i=1, j=1：'a' != 'c'
    dp[0][1] = "", dp[1][0] = ""，长度均为 0，取 ""。

  • i=1, j=2：'a' == 'a'
    dp[0][1] = "" + 'a' = "a"

  • i=1, j=3：'a' != 'b'
    上 dp[0][3] = ""，左 dp[1][2] = "a"，左更长，取 "a"。

第一行结果：
dp[1][1]="", dp[1][2]="a", dp[1][3]="a"。

  • i=2, j=1：'b' != 'c'
    上 dp[1][1]=""，左 dp[2][0]=""，长度相等，字典序相等，取 ""。

  • i=2, j=2：'b' != 'a'
    上 dp[1][2]="a"，左 dp[2][1]=""，上更长，取 "a"。

  • i=2, j=3：'b' == 'b'
    dp[1][2]="a" + 'b' = "ab"

第二行结果：
dp[2][1]="", dp[2][2]="a", dp[2][3]="ab"。

  • i=3, j=1：'a' != 'c'
    上 dp[2][1]=""，左 dp[3][0]=""，取 ""。

  • i=3, j=2：'a' == 'a'
    dp[2][1]="" + 'a' = "a"

  • i=3, j=3：'a' != 'b'
    上 dp[2][3]="ab"，左 dp[3][2]="a"，上更长，取 "ab"。

第三行结果：
dp[3][1]="", dp[3][2]="a", dp[3][3]="ab"。

  • i=4, j=1：'c' == 'c'
    dp[3][0]="" + 'c' = "c"

  • i=4, j=2：'c' != 'a'
    上 dp[3][2]="a"，左 dp[4][1]="c"，长度均为 1，选字典序更小：比较 "a" 与 "c"，"a" 更小，取 "a"。

  • i=4, j=3：'c' != 'b'
    上 dp[3][3]="ab"，左 dp[4][2]="a"，上更长，取 "ab"。

最终 dp[4][3] = "ab"，即为字典序最小的 LCS。

第四步：算法复杂度与优化

上述方法的空间复杂度是 O(n×m×L)，L 是 LCS 字符串长度（最坏 O(min(n,m))），存储每个 dp[i][j] 的字符串可能较长。
时间也是 O(n×m×L) 因为字符串拼接比较有开销。

可以优化：

  1. 先求 dp_len[i][j] 记录长度。
  2. 再反向构造最小字典序 LCS：
    • 从 (n, m) 开始，若字符相等，加入结果，然后向左上走。
    • 若不等，比较 dp_len[i-1][j] 和 dp_len[i][j-1]：
      • 如果左边 > 上面：向左走。
      • 如果上面 > 左边：向上走。
      • 如果相等：要选字典序更小的路径，这需要预知两种方向最终会得到的 LCS 字符串，但我们可以用一个巧妙方法：
        从 (i-1, j) 和 (i, j-1) 的位置开始，同时走 LCS 构造，比较它们下一步会得到的字符，选能得到更小字符的那条路。
        但这样每次决策都要递归，会慢。

更高效的做法是：
在反向追踪时，如果出现 dp_len[i-1][j] == dp_len[i][j-1]，我们看 text1[i-1] 与 text2[j-1] 哪个字符的 ASCII 码更小？
不对，因为 text1[i-1] 和 text2[j-1] 都不一定在 LCS 中。
实际需要比较的是：
假设我们向上走，最终得到的 LCS 字符串的第一个字符（因为我们从后往前构造，所以是最后一个字符）是什么？
我们可以预先用另一个 DP 记录从每个状态出发能得到的最小字典序 LCS 的第一个字符，但这样要正反两次 DP，较为复杂。

一个实际可行且简单的办法：
在正向 DP 长度后，再用一个 DP 数组 best[i][j] 存储从 (i,j) 到 (n,m) 能构造的字典序最小 LCS（注意是从当前位置往后，不是全局）。
这样 best[0][0] 就是答案。

第五步：实际简单实现方法（长度优先，字典序其次）

我们可以用字符串直接 DP，虽然占用空间，但代码直观。对于较短字符串（几百长度）是可行的。
核心就是前面第三步的递推，比较规则：

  • 优先比长度，长度大的胜出。
  • 长度相同，选字典序小的。

这样保证了每一步都保留最小字典序的 LCS。

第六步：示例完整计算验证

用前面的例子，最终得到 "ab"。

再举一例：text1 = "abcbdab", text2 = "bdcaba"
LCS 长度 = 4，可能的 LCS 有："bdab"、"bcab"、"bcba" 等。
字典序最小的是 "bcab"。

用我们的 DP 方法：
在状态 (7,6) 处，最终算得 dp[7][6] = "bcab"，验证正确。

总结

  1. 基础 LCS 问题用 dp[i][j] 记录长度。
  2. 若要字典序最小的 LCS，可以在 DP 过程中直接记录字符串，按长度优先、字典序其次的规则选择。
  3. 时间复杂度 O(n×m×L)，空间 O(n×m×L)（可优化为 O(n×m) 存储字符串引用）。
  4. 适用于中等长度字符串，若字符串很长，需要更精细的优化（比如只存路径方向并比较字典序）。
最长公共子序列问题中的字典序最小解 题目描述 给定两个字符串 text1 和 text2 ，要求找出它们的最长公共子序列（Longest Common Subsequence, LCS）。但此题不仅要求长度，还需要输出 字典序最小 的 LCS。 若有多个 LCS 满足长度最长，则返回其中字典序最小的那个（按字符的 ASCII 码比较顺序）。 例如： 输入： text1 = "abac" , text2 = "cab" 所有 LCS 为： "ab" 、 "ac" 、 "cb" ，长度均为 2；其中字典序最小的为 "ab" 。 输入： text1 = "abcde" , text2 = "ace" 唯一 LCS 为 "ace" ，长度为 3。 第一步：回顾基础 LCS 长度的求法 经典 LCS 长度问题用动态规划： 定义 dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的 LCS 长度（i、j 从 1 开始）。 转移方程： 若 text1[i-1] == text2[j-1] ： dp[i][j] = dp[i-1][j-1] + 1 否则： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 边界： dp[0][j] = dp[i][0] = 0 。 例如 ： text1 = "abac" , text2 = "cab" ，得到的 dp 矩阵如下（纵向 text1，横向 text2）： | | | c | a | b | |---|--:|--:|--:|--:| | | 0 | 0 | 0 | 0 | | a | 0 | 0 | 1 | 1 | | b | 0 | 0 | 1 | 2 | | a | 0 | 0 | 1 | 2 | | c | 0 | 1 | 1 | 2 | LCS 长度为 dp[4][3] = 2 。 第二步：引入字典序最小的 LCS 构造 我们需要在求长度的同时，记录所有能构成最长公共子序列的字符串中字典序最小的。 思路： 先按常规 DP 求出 LCS 长度。 然后 反向追踪 所有可能的 LCS 字符串，再选最小的。 反向追踪时，若两字符相等，则该字符属于某个 LCS，加入结果，然后 i--, j-- 。 若字符不等，则看 dp[i-1][j] 与 dp[i][j-1] 谁更大，往更大的方向走（保证还在最长序列的路径上）；如果两边一样大，则需要考虑哪条路径最终产生的字符串字典序更小。 难点：如果两边一样大（即向上或向左都可行），我们不能随便选一个方向，因为不同方向会导致最终得到的 LCS 字符串不同，可能字典序不一样。 关键观察 ： 假设我们现在在 (i, j) ， text1[i-1] != text2[j-1] ，且 dp[i-1][j] == dp[i][j-1] ，那么： 向上走 (i-1, j) 意味着忽略 text1[i-1] 。 向左走 (i, j-1) 意味着忽略 text2[j-1] 。 这两条路径最终得到的 LCS 字符串可能是不同的，我们需要选一个将来能得到 字典序最小 的 LCS 的方向。 如何比较？ 可以这样想：我们从 (i, j) 开始，最终构造的 LCS 字符串是从后往前构建的（因为我们是反向追踪）。 字典序比较是从前向后比较，但是反向追踪时，我们得到的字符是逆序的（最后一个字符先得到）。 如果我们希望最终字符串字典序最小，那么在 同样长度 的情况下，应该 尽早出现较小的字符 。 但在反向过程中，我们无法预知前面会有什么字符，除非我们预先知道所有可能的 LCS 字符串——这需要搜索所有路径，成本较高。 第三步：另一种解法——同时递推 LCS 字符串 定义 dp[i][j] 为 (i, j) 状态对应的 字典序最小的 LCS 字符串（而不只是长度）。这样递推时需要同时考虑长度优先，其次字典序。 递推方法： 如果 text1[i-1] == text2[j-1] ： 新的 LCS = dp[i-1][j-1] + text1[i-1] 。 否则： 候选1 = dp[i-1][j] 候选2 = dp[i][j-1] 先比较长度：选长度更大的；如果长度相等，选字典序更小的。 边界： dp[i][0] 和 dp[0][j] 都是空字符串 "" 。 这样， dp[n][m] 就是答案。 例子演示 ： text1 = "abac" , text2 = "cab" 初始化： dp[0][*] = "" ， dp[*][0] = "" 逐行计算（记录 dp[i][j] 字符串）： i=1, j=1 ： 'a' != 'c' dp[0][1] = "" , dp[1][0] = "" ，长度均为 0，取 "" 。 i=1, j=2 ： 'a' == 'a' dp[0][1] = "" + 'a' = "a" i=1, j=3 ： 'a' != 'b' 上 dp[0][3] = "" ，左 dp[1][2] = "a" ，左更长，取 "a" 。 第一行结果： dp[1][1]="" , dp[1][2]="a" , dp[1][3]="a" 。 i=2, j=1 ： 'b' != 'c' 上 dp[1][1]="" ，左 dp[2][0]="" ，长度相等，字典序相等，取 "" 。 i=2, j=2 ： 'b' != 'a' 上 dp[1][2]="a" ，左 dp[2][1]="" ，上更长，取 "a" 。 i=2, j=3 ： 'b' == 'b' dp[1][2]="a" + 'b' = "ab" 第二行结果： dp[2][1]="" , dp[2][2]="a" , dp[2][3]="ab" 。 i=3, j=1 ： 'a' != 'c' 上 dp[2][1]="" ，左 dp[3][0]="" ，取 "" 。 i=3, j=2 ： 'a' == 'a' dp[2][1]="" + 'a' = "a" i=3, j=3 ： 'a' != 'b' 上 dp[2][3]="ab" ，左 dp[3][2]="a" ，上更长，取 "ab" 。 第三行结果： dp[3][1]="" , dp[3][2]="a" , dp[3][3]="ab" 。 i=4, j=1 ： 'c' == 'c' dp[3][0]="" + 'c' = "c" i=4, j=2 ： 'c' != 'a' 上 dp[3][2]="a" ，左 dp[4][1]="c" ，长度均为 1，选字典序更小：比较 "a" 与 "c" ， "a" 更小，取 "a" 。 i=4, j=3 ： 'c' != 'b' 上 dp[3][3]="ab" ，左 dp[4][2]="a" ，上更长，取 "ab" 。 最终 dp[4][3] = "ab" ，即为字典序最小的 LCS。 第四步：算法复杂度与优化 上述方法的空间复杂度是 O(n×m×L)，L 是 LCS 字符串长度（最坏 O(min(n,m))），存储每个 dp[i][j] 的字符串可能较长。 时间也是 O(n×m×L) 因为字符串拼接比较有开销。 可以优化： 先求 dp_len[i][j] 记录长度。 再反向构造最小字典序 LCS： 从 (n, m) 开始，若字符相等，加入结果，然后向左上走。 若不等，比较 dp_len[i-1][j] 和 dp_len[i][j-1] ： 如果左边 > 上面：向左走。 如果上面 > 左边：向上走。 如果相等：要选字典序更小的路径，这需要预知两种方向最终会得到的 LCS 字符串，但我们可以用一个巧妙方法： 从 (i-1, j) 和 (i, j-1) 的位置开始， 同时走 LCS 构造 ，比较它们下一步会得到的字符，选能得到更小字符的那条路。 但这样每次决策都要递归，会慢。 更高效的做法是： 在反向追踪时，如果出现 dp_len[i-1][j] == dp_len[i][j-1] ，我们看 text1[i-1] 与 text2[j-1] 哪个字符的 ASCII 码更小？ 不对，因为 text1[i-1] 和 text2[j-1] 都不一定在 LCS 中。 实际需要比较的是： 假设我们向上走，最终得到的 LCS 字符串的第一个字符（因为我们从后往前构造，所以是最后一个字符）是什么？ 我们可以预先用另一个 DP 记录从每个状态出发能得到的最小字典序 LCS 的第一个字符，但这样要正反两次 DP，较为复杂。 一个实际可行且简单的办法： 在正向 DP 长度后，再用一个 DP 数组 best[i][j] 存储从 (i,j) 到 (n,m) 能构造的 字典序最小 LCS（注意是从当前位置往后，不是全局）。 这样 best[0][0] 就是答案。 第五步：实际简单实现方法（长度优先，字典序其次） 我们可以用字符串直接 DP，虽然占用空间，但代码直观。对于较短字符串（几百长度）是可行的。 核心就是前面第三步的递推，比较规则： 优先比长度，长度大的胜出。 长度相同，选字典序小的。 这样保证了每一步都保留最小字典序的 LCS。 第六步：示例完整计算验证 用前面的例子，最终得到 "ab" 。 再举一例： text1 = "abcbdab" , text2 = "bdcaba" LCS 长度 = 4，可能的 LCS 有： "bdab" 、 "bcab" 、 "bcba" 等。 字典序最小的是 "bcab" 。 用我们的 DP 方法： 在状态 (7,6) 处，最终算得 dp[7][6] = "bcab" ，验证正确。 总结 基础 LCS 问题用 dp[i][j] 记录长度。 若要字典序最小的 LCS，可以在 DP 过程中直接记录字符串，按 长度优先、字典序其次 的规则选择。 时间复杂度 O(n×m×L)，空间 O(n×m×L)（可优化为 O(n×m) 存储字符串引用）。 适用于中等长度字符串，若字符串很长，需要更精细的优化（比如只存路径方向并比较字典序）。