1771. 由子序列构造的最长回文串的长度

发表于 2026-01-19 分类于力扣阅读次数： Waline：本文字数： 1k 阅读时长 ≈ 3 分钟

考点

区间DP
回文序列

思路

一、问题概述

给定两个字符串：

word1
word2

允许分别从二者中选取子序列，将选出的两个子序列拼接后构成一个字符串，要求该字符串是回文串，并且至少使用 word1 和 word2 中各一个字符。

目标是： 最大化该回文串的长度。

二、问题建模思路

2.1 关键观察

子序列问题通常可以通过 动态规划（DP） 建模；
回文结构具有明显的 区间性质，天然适合使用「区间 DP」；
题目额外要求：
- 回文串必须同时使用 word1 与 word2 的字符。

为统一建模，先进行如下处理。

2.2 字符串拼接

将两个字符串拼接成一个新串： \[ s = \text{word1} + \text{word2} \] 设：

\(|\text{word1}| = n\)
\(|s| = m\)

则：

下标区间 \([1, n]\) 属于 word1
下标区间 \([n+1, m]\) 属于 word2

三、状态定义（State）

定义二维 DP 数组： \[ f[i][j] = \text{字符串 } s[i \dots j] \text{ 的最长回文子序列长度} \] 其中：

\(1 \le i \le j \le m\)
使用 1-based index 方便表述

这是一个标准的最长回文子序列（LPS）定义。

四、状态转移方程（Transition）

4.1 基础状态（Base Case）

单个字符天然是长度为 1 的回文串： \[ f[i][i] = 1 \quad (1 \le i \le m) \]

4.2 状态转移

考虑区间 \([i, j]\)，比较两端字符 \(s[i]\) 与 \(s[j]\)：

情况一：两端字符相等

\[ s[i] = s[j] \]

则可以将二者作为回文的对称两端： \[ f[i][j] = f[i+1][j-1] + 2 \]

情况二：两端字符不等

\[ s[i] \ne s[j] \]

只能舍弃一侧字符，取较优子问题： \[ f[i][j] = \max\bigl(f[i+1][j],\; f[i][j-1]\bigr) \]

4.3 遍历顺序

由于状态 \(f[i][j]\) 依赖于：

\(f[i+1][j-1]\)
\(f[i+1][j]\)
\(f[i][j-1]\)

因此必须保证 区间更小的状态已被计算。

采用标准遍历顺序：

\(i\) 从 大到小
\(j\) 从 小到大

即：

1 2	for i = m → 1: for j = i+1 → m:

五、答案的提取（关键约束）

5.1 额外约束的处理方式

题目要求回文串 必须同时使用 word1 和 word2 的字符。

在拼接串 s 中，这等价于： \[ i \le n \quad \text{且} \quad j > n \] 即：

左端点来自 word1
右端点来自 word2

5.2 答案更新策略

在状态转移中，只有当以下条件同时满足时，才用该状态更新答案：

\(s[i] = s[j]\)（形成一对回文端点）
\(i \le n\) 且 \(j > n\)

此时： \[ \text{ans} = \max(\text{ans}, f[i][j]) \] 这样可以保证：

回文子序列一定使用了 word1 与 word2 的字符；
不需要额外增加维度或标记，逻辑简洁。

六、时间与空间复杂度分析

时间复杂度： \[ O(m^2) \]
空间复杂度： \[ O(m^2) \]

其中 \(m = |\text{word1}| + |\text{word2}|\)，在题目限制下是可接受的。

七、完整代码（附详细注释）

class Solution {
public:
    static const int maxn = 2e3 + 5;

    int longestPalindrome(string word1, string word2) {
        // f[i][j]: s[i..j] 的最长回文子序列长度（1-based）
        int f[maxn][maxn] = {};

        int n = word1.size();          // word1 的长度
        string s = word1 + word2;      // 拼接字符串
        int m = s.size();              // 拼接后总长度

        // Base case: 单个字符是长度为 1 的回文
        for (int i = 1; i <= m; ++i)
            f[i][i] = 1;

        int ans = 0;

        // 区间 DP：i 从大到小，j 从小到大
        for (int i = m; i >= 1; --i) {
            for (int j = i + 1; j <= m; ++j) {
                if (s[i - 1] == s[j - 1]) {
                    // 两端字符相等，可作为回文的对称端点
                    f[i][j] = f[i + 1][j - 1] + 2;

                    // 左端来自 word1，右端来自 word2
                    // 保证回文子序列同时使用了两个字符串
                    if (i <= n && j > n)
                        ans = max(ans, f[i][j]);
                } else {
                    // 两端字符不等，舍弃一端
                    f[i][j] = max(f[i][j - 1], f[i + 1][j]);
                }
            }
        }

        return ans;
    }
};