class Solution {
public:
int longestPalindrome(string word1, string word2) {
}
};
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 <= 1000word1 和 word2 由小写英文字母组成原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 45.6 MB, 提交时间: 2023-10-27 22:11:29
func longestPalindrome(word1, word2 string) (ans int) {
s := word1 + word2
n := len(s)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
f[i][i] = 1
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
f[i][j] = f[i+1][j-1] + 2
if i < len(word1) && j >= len(word1) {
ans = max(ans, f[i][j]) // f[i][j] 一定包含 s[i] 和 s[j]
}
} else {
f[i][j] = max(f[i+1][j], f[i][j-1])
}
}
}
return
}
func max(a, b int) int { if a < b { return b }; return a }
cpp 解法, 执行用时: 36 ms, 内存消耗: 24.1 MB, 提交时间: 2023-10-27 22:11:13
class Solution {
public:
int longestPalindrome(string word1, string word2) {
auto s = word1 + word2;
int ans = 0, n = s.length(), f[n][n];
memset(f, 0, sizeof(f));
for (int i = n - 1; i >= 0; --i) {
f[i][i] = 1;
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j]) {
f[i][j] = f[i + 1][j - 1] + 2;
if (i < word1.length() && j >= word1.length()) {
ans = max(ans, f[i][j]); // f[i][j] 一定包含 s[i] 和 s[j]
}
} else {
f[i][j] = max(f[i + 1][j], f[i][j - 1]);
}
}
}
return ans;
}
};
java 解法, 执行用时: 21 ms, 内存消耗: 71.6 MB, 提交时间: 2023-10-27 22:10:57
class Solution {
public int longestPalindrome(String word1, String word2) {
char[] s = (word1 + word2).toCharArray();
int ans = 0, n = s.length;
int[][] f = new int[n][n];
for (int i = n - 1; i >= 0; --i) {
f[i][i] = 1;
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j]) {
f[i][j] = f[i + 1][j - 1] + 2;
if (i < word1.length() && j >= word1.length()) {
ans = Math.max(ans, f[i][j]); // f[i][j] 一定包含 s[i] 和 s[j]
}
} else {
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
}
}
}
return ans;
}
}
python3 解法, 执行用时: 1384 ms, 内存消耗: 68.5 MB, 提交时间: 2023-10-27 22:10:41
class Solution:
def longestPalindrome(self, word1: str, word2: str) -> int:
s = word1 + word2
ans, n = 0, len(s)
f = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
f[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
f[i][j] = f[i + 1][j - 1] + 2
if i < len(word1) <= j:
ans = max(ans, f[i][j]) # f[i][j] 一定包含 s[i] 和 s[j]
else:
f[i][j] = max(f[i + 1][j], f[i][j - 1])
return ans
def longestPalindrome2(self, word1: str, word2: str) -> int:
s = word1 + word2
ans = 0
@cache
def dfs(i: int, j: int) -> int:
if i > j: return 0
if i == j: return 1
if s[i] == s[j]:
res = dfs(i + 1, j - 1) + 2
if i < len(word1) <= j:
nonlocal ans
ans = max(ans, res)
return res
return max(dfs(i + 1, j), dfs(i, j - 1))
dfs(0, len(s) - 1)
return ans