淘宝搜索排名,山东网站优化公司,全网推广图片,培训心得体会万能模板文章目录1. 题目2. 解题1. 题目
给你两个字符串 word1 和 word2 #xff0c;请你按下述方法构造一个字符串#xff1a;
从 word1 中选出某个 非空 子序列 subsequence1 。从 word2 中选出某个 非空 子序列 subsequence2 。连接两个子序列 subsequence1 subsequence2 …
文章目录1. 题目2. 解题1. 题目
给你两个字符串 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 由小写英文字母组成来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximize-palindrome-length-from-subsequences 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考 LeetCode 516. 最长回文子序列动态规划将两个字符串拼接题目要求非空在516题基础上稍加限制即可
class Solution {
public:int longestPalindrome(string word1, string word2) {string s word1 word2;int n s.size(), n1 word1.size();vectorvectorint dp(n, vectorint(n, 0));int ans 0;for(int i 0; i n; i){dp[i][i] 1;for(int j i-1; j 0; --j){if(s[i] s[j]){dp[j][i] dp[j1][i-1]2;if(j n1 i n1)ans max(ans, dp[j][i]);}elsedp[j][i] max(dp[j1][i], dp[j][i-1]); }}return ans;}
};228 ms 69 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
