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

问题描述#

给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：

从 word1 中选出某个非空子序列 subsequence1 。

从 word2 中选出某个非空子序列 subsequence2 。

连接两个子序列 subsequence1 + subsequence2 ，得到字符串。

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

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

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

示例 1：
输入：word1 = "cacb", word2 = "cbba"
输出：5
解释：从 word1 中选出 "ab" ，从 word2 中选出 "cba" ，得到回文串 "abcba" 。
示例 2：
输入：word1 = "ab", word2 = "ab"
输出：3
解释：从 word1 中选出 "ab" ，从 word2 中选出 "a" ，得到回文串 "aba" 。
示例 3：
输入：word1 = "aa", word2 = "bb"
输出：0
解释：无法按题面所述方法构造回文串，所以返回 0 。
提示：

1 <= word1.length, word2.length <= 1000

word1 和 word2 由小写英文字母组成

解题思路#

如何求单个字符串中的最长回文子序列？516. 最长回文子序列这道题说明了这个问题。

如果我们把本题中的两个字符串合成一个考虑，与 516 题就很类似了，但是本题还有一个约束就是，它要求从两个字符串中取出的子序列是非空的。

在 516 题中，使用动态规划的数组 \(\texttt{dp}[i][j]\) 记录了子串 \(S_{i\dots j}\) 中的最长回文子序列，为了满足本题子序列非空的要求，我们可以限制只比较 \(i\lt\texttt{len(s1)},j\ge\texttt{len(s1)}\)。

Python

class Solution:
    def longestPalindrome(self, s1: str, s2: str) -> int:
        s = s1 + s2
        n, n1 = len(s), len(s1)
        dp = [[0] * n for _ in range(n)]
        ans = 0

        for j in range(n):
            dp[j][j] = 1
            for i in range(j - 1, -1, -1):
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i + 1][j - 1]
                    if i < n1 and j >= n1:
                        ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

        return ans

C++

class Solution {
public:
    int longestPalindrome(string s1, string s2) {
        string s = s1 + s2;
        int n = s.size(), n1 = s1.size();
        vector<vector<int>> dp(n, vector<int>(n));
        int ans = 0;

        for (int j = 0; j < n; ++j) {
            dp[j][j] = 1;
            for (int i = j - 1; i >= 0; --i) {
                if (s[i] == s[j]) {
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                    if (i < n1 && j >= n1) {
                        ans = max(ans, dp[i][j]);
                    }
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return ans;
    }
};

时间复杂度：\(\mathcal{O}((m+n)^2)\)
空间复杂度：\(\mathcal{O}((m+n)^2)\)

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

问题描述#

解题思路#

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