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

题目描述

给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：
- 从 word1 中选出某个 非空 子序列 subsequence1 。
- 从 word2 中选出某个 非空 子序列 subsequence2 。
- 连接两个子序列 subsequence1 + subsequence2 ，得到字符串。

返回可按上述方法构造的最长 回文串 的 长度 。如果无法构造回文串，返回 0 。

字符串 s 的一个 子序列 是通过从 s 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。

回文串 是正着读和反着读结果一致的字符串。

数据范围

• 1 <= word1.length, word2.length <= 1000
• word1 和 word2 由小写英文字母组成

示例1：

输入：word1 = "cacb", word2 = "cbba"
输出：5
解释：从 word1 中选出 "ab" ，从 word2 中选出 "cba" ，得到回文串 "abcba" 。

示例2：

输入：word1 = "ab", word2 = "ab"
输出：3
解释：从 word1 中选出 "ab" ，从 word2 中选出 "a" ，得到回文串 "aba" 。

算法1：

区间DP + 线性DP

回文串为前后对称的字符串，将第二个字符串逆置，问题变成了：前部找一个最长公共子序列，后部找一个最长回文子串，枚举每一个位置，找出两者之和的最大值

所以要用三次DP，对两串求最长公共子序列，对a串求最长回文字串，对b串求最长回文子串

注意：求最长回文子串时，因为不是连续的取，所以要对f[i + 1, j], f[i, j - 1]，f[i + 1, j - 1] + 2取最值，而Lc 5.最长回文子串是一个连续的串，所以只需要看f[i + 1, j - 1]。

时间复杂度

$O(n^2)$：三个DP都是n^2，最终复杂度为n^2

参考文献

yxc

C++ 代码

const int N = 1010;
class Solution {
public:
    int f1[N][N], f2[N][N], f3[N][N];
    void work(string &s, int f[][N]){
        int n = s.size();
        for(int len = 1; len <= n; len++){
            for(int i = 1; i + len - 1 <= n; i++){
                int j = i + len - 1;
                if(len == 1) f[i][j] = 1;
                else {
                    f[i][j] = max(f[i + 1][j], f[i][j - 1]);
                    if(s[i - 1] == s[j - 1]) f[i][j] = max(f[i][j], f[i + 1][j - 1] + 2);
                }
            }
        }
    }
    int longestPalindrome(string a, string b) {
        int n = a.size(), m = b.size();
        reverse(b.begin(), b.end());
        work(a, f2), work(b, f3);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f1[i][j] = max(f1[i - 1][j], f1[i][j - 1]);
                if(a[i - 1] == b[j - 1]) f1[i][j] = max(f1[i][j], f1[i - 1][j - 1] + 1);
            }
        }
        int res = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(f1[i][j])
                    res = max(res, f1[i][j] * 2 + max(f2[i + 1][n], f3[j + 1][m]));
            }
        }
        return res;
    }
};