| 日期 |
2022年9月15日 |
| 是否独立完成 |
否（差一点点！） |
| 涉及算法 |
动态规划Again |
题面
LeetCode 1771. 由子序列构造的最长回文串的长度
给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：
- 从
word1 中选出某个 非空 子序列 subsequence1 。
- 从
word2 中选出某个 非空 子序列 subsequence2 。
- 连接两个子序列
subsequence1 + subsequence2 ，得到字符串。
返回可按上述方法构造的最长 回文串 的 长度 。如果无法构造回文串，返回 0 。
字符串 s 的一个 子序列 是通过从 s 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。
回文串 是正着读和反着读结果一致的字符串。
示例 1：
1
2
3
| 输入：word1 = "cacb", word2 = "cbba"
输出：5
解释：从 word1 中选出 "ab" ，从 word2 中选出 "cba" ，得到回文串 "abcba" 。
|
示例 2：
1
2
3
| 输入：word1 = "ab", word2 = "ab"
输出：3
解释：从 word1 中选出 "ab" ，从 word2 中选出 "a" ，得到回文串 "aba" 。
|
示例 3：
1
2
3
| 输入：word1 = "aa", word2 = "bb"
输出：0
解释：无法按题面所述方法构造回文串，所以返回 0 。
|
题解
动态规划
怎么Hard题这么多动态规划啊。而且与回文串有关的题题号也恰好是回文的，有点巧妙。
一开始的思路是把word2给reverse一下，然后通过动态规划算word1和word2的最长公共子序列，就可以得到答案了。但是遇到了下面这个测试用例WA了。
1
2
| string word1 = "afaaadacb";
string word2 = "ca";
|
WA后初步认为是两个串不一样长导致的，所以添加了平衡字符串长度的代码，然后发现并不是长度的原因。还是得把两个串合在一起dp，并只在两个子串都不为空时更新答案。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int longestPalindrome(string word1, string word2) {
int n1 = word1.length(), n2 = word2.length();
int n = n1 + n2;
string word = word1 + word2;
vector<vector<int>> dp(n, vector<int>(n, 0));
int res = (word[n1 - 1] == word[n1]) ? 2 : 0;
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int i = 0; i < n - 1; i++) dp[i][i + 1] = (word[i] == word[i + 1]) ? 2 : 1;
for (int l = 2; l < n; l++) {
for (int i = 0; i + l < n; i++) {
int j = i + l;
if (word[i] == word[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
if (i < n1 && j >= n1) res = max(res, dp[i][j]);
}
else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
}
}
return res;
}
};
|
有的没的
没事听点歌（Knock 2 - dashstar*）