赞
踩
给你两个字符串 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 由小写英文字母组成
word3 = word1 + word2
n1 = word1.length
n2 = word2.length
n = word3.length
dp[i][j] 表示 words[i…j-1]的最长回文子序列。
空间复杂度: O(nn)
dp[i][j] = max(dp[i+1][j],dp[i][j-1]
如果words[i] 等于words[j], dp[i][j] = MaxSelf( dp[i+1][j-1])+2)
单个状态转移的时间复杂度:O(1)
故总的时间复杂度为:O(nn)
d
p
[
i
]
[
j
]
=
{
d
p
[
i
]
[
j
−
1
]
d
p
[
j
−
1
]
不在回文串中
d
p
[
i
+
1
]
[
j
−
1
]
s
[
i
]
和
s
[
j
−
1
]
对应
d
p
[
i
+
1
]
[
j
]
s
[
j
−
1
]
和其它字符对应
dp[i][j] =
长度为1的子串 dp[i][j]全部为1,长度为0的子串,dp[i][j]全部为0。
len 从2到N
( i < n1 )&& ( j >= n1) 最大值 (2+dp[i+1][j])
回文串的首字符必须在word1,尾字符必须在word2。
template<class ELE> void MaxSelf(ELE* seft, const ELE& other) { *seft = max(*seft, other); } class Solution { public: int longestPalindrome(string word1, string word2) { string s = word1 + word2; const auto N1 = word1.length(); const int N = s.length(); vector<vector<int>> dp(N, vector<int>(N+1, 0)); for (int i = 0; i < N; i++) { dp[i][i+1] = 1; } for (int len = 2; len <= N; len++) { for (int left = 0; left + len <= N; left++) { dp[left][left + len] = max(dp[left+1][left + len], dp[left][left + len-1]); if (s[left] == s[left + len - 1]) { MaxSelf(&dp[left][left + len], dp[left + 1][left + len - 1] + 2); } } } int iRet = 0; for (int i = 0; i < N1; i++) { for (int j = N1; j < N; j++) { if( s[i] == s[j]){ MaxSelf(&iRet, dp[i + 1][j] + 2); } } } return iRet; } };
template<class T1, class T2> void AssertEx(const T1& t1, const T2& t2) { Assert::AreEqual(t1, t2); } template<class T> void AssertEx(const vector<T>& v1, const vector<T>& v2) { Assert::AreEqual(v1.size(), v2.size()); for (int i = 0; i < v1.size(); i++) { Assert::AreEqual(v1[i], v2[i]); } } template<class T> void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2) { sort(vv1.begin(), vv1.end()); sort(vv2.begin(), vv2.end()); Assert::AreEqual(vv1.size(), vv2.size()); for (int i = 0; i < vv1.size(); i++) { AssertEx(vv1[i], vv2[i]); } } namespace UnitTest { string word1, word2; TEST_CLASS(UnitTest) { public: TEST_METHOD(TestMethod0) { word1 = "cacb", word2 = "cbba"; auto res = Solution().longestPalindrome(word1, word2); AssertEx(5, res); } TEST_METHOD(TestMethod1) { word1 = "ab", word2 = "ab"; auto res = Solution().longestPalindrome(word1, word2); AssertEx(3, res); } TEST_METHOD(TestMethod2) { word1 = "aa", word2 = "bb"; auto res = Solution().longestPalindrome(word1, word2); AssertEx(0, res); } TEST_METHOD(TestMethod3) { word1 = "a", word2 = "a"; auto res = Solution().longestPalindrome(word1, word2); AssertEx(2, res); } TEST_METHOD(TestMethod4) { word1 = "rhuzwqohquamvsz", word2 = "kvunbxje"; auto res = Solution().longestPalindrome(word1, word2); AssertEx(7, res); } TEST_METHOD(TestMethod5) { word1 = "wqo", word2 = "hquamvs"; auto res = Solution().longestPalindrome(word1, word2); AssertEx(3, res); } TEST_METHOD(TestMethod6) { word1 = "wqo", word2 = "hq"; auto res = Solution().longestPalindrome(word1, word2); AssertEx(3, res); } TEST_METHOD(TestMethod7) { word1 = "qo", word2 = "hq"; auto res = Solution().longestPalindrome(word1, word2); AssertEx(3, res); } TEST_METHOD(TestMethod8) { word1 = "qo", word2 = "q"; auto res = Solution().longestPalindrome(word1, word2); AssertEx(3, res); } }; }
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
我想对大家说的话 |
---|
《喜缺全书算法册》以原理、正确性证明、总结为主。 |
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。