Hard

题目描述

给定两个字符串 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 由小写英文字母组成

解题思路

这道题的关键在于理解题意：我们需要从 word1 和 word2 分别选择非空子序列，然后拼接成回文串。

核心思路：

  1. 将两个字符串拼接成一个字符串 s = word1 + word2
  2. 使用动态规划求最长回文子序列，但需要确保选择的子序列满足条件：必须包含来自 word1 的字符和来自 word2 的字符
  3. 设 dp[i][j] 表示字符串 s[i...j] 中的最长回文子序列长度

状态转移：

  • 如果 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1] + 2
  • 否则 dp[i][j] = max(dp[i+1][j], dp[i][j-1])

关键约束处理： 为了确保子序列同时包含来自两个字符串的字符，我们需要枚举所有可能的起始和结束位置：

  • 起始位置必须在 word1 中（索引 < word1.length）
  • 结束位置必须在 word2 中（索引 >= word1.length）
  • 当 s[i] == s[j] 且 i < word1.length 且 j >= word1.length 时，更新答案

这样确保了构造的回文串确实包含来自两个字符串的字符。

代码实现

class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        string s = word1 + word2;
        int n = s.length();
        int n1 = word1.length();
        
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // 单个字符的回文长度为1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        
        int result = 0;
        
        // 从长度2开始填充dp表
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                    // 检查是否满足条件：i在word1中，j在word2中
                    if (i < n1 && j >= n1) {
                        result = max(result, dp[i][j]);
                    }
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        n = len(s)
        n1 = len(word1)
        
        dp = [[0] * n for _ in range(n)]
        
        # 单个字符的回文长度为1
        for i in range(n):
            dp[i][i] = 1
        
        result = 0
        
        # 从长度2开始填充dp表
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                    # 检查是否满足条件：i在word1中，j在word2中
                    if i < n1 and j >= n1:
                        result = max(result, dp[i][j])
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        
        return result

public class Solution {
    public int LongestPalindrome(string word1, string word2) {
        string s = word1 + word2;
        int n = s.Length;
        int n1 = word1.Length;
        
        int[,] dp = new int[n, n];
        
        // 单个字符的回文长度为1
        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }
        
        int result = 0;
        
        // 从长度2开始填充dp表
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                if (s[i] == s[j]) {
                    dp[i, j] = dp[i + 1, j - 1] + 2;
                    // 检查是否满足条件：i在word1中，j在word2中
                    if (i < n1 && j >= n1) {
                        result = Math.Max(result, dp[i, j]);
                    }
                } else {
                    dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]);
                }
            }
        }
        
        return result;
    }
}

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var longestPalindrome = function(word1, word2) {
    const s = word1 + word2;
    const n = s.length;
    const n1 = word1.length;
    
    // dp[i][j] = length of longest palindromic subsequence in s[i...j]
    const dp = Array(n).fill().map(() => Array(n).fill(0));
    
    // Base case: single characters
    for (let i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    let result = 0;
    
    // Fill dp table
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
                
                // Check if this palindrome uses characters from both words
                if (i < n1 && j >= n1) {
                    result = Math.max(result, dp[i][j]);
                }
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)其中 n = len(word1) + len(word2)，需要填充 n×n 的 DP 表
空间复杂度O(n²)DP 表的空间开销

相关题目