【C++ 贪心】1616. 分割两个字符串得到回文串|1868

本文涉及知识点

C++贪心

LeetCode1616. 分割两个字符串得到回文串

给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： aprefix 和 asuffix ，满足 a = aprefix + asuffix ，同理，由 b 可以得到两个字符串 bprefix 和 bsuffix ，满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。
当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix 可以为空。比方说， s = “abc” 那么 “” + “abc” ， “a” + “bc” ， “ab” + “c” 和 “abc” + “” 都是合法分割。
如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
注意， x + y 表示连接字符串 x 和 y 。
示例 1：
输入：a = “x”, b = “y”
输出：true
解释：如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割：
aprefix = “”, asuffix = “x”
bprefix = “”, bsuffix = “y”
那么 aprefix + bsuffix = “” + “y” = “y” 是回文串。
示例 2：
输入：a = “xbdef”, b = “xecab”
输出：false
示例 3：
输入：a = “ulacfd”, b = “jizalu”
输出：true
解释：在下标为 3 处分割：
aprefix = “ula”, asuffix = “cfd”
bprefix = “jiz”, bsuffix = “alu”
那么 aprefix + bsuffix = “ula” + “alu” = “ulaalu” 是回文串。
提示：
1 <= a.length, b.length <= 10⁵
a.length == b.length
a 和 b 都只包含小写英文字母

贪心

f(a,b) 判断a的前缀+b的后缀能否构成回文。返回值：f(a,b) || f(b,a)。
令最优解len1 = min(a前缀的长度,b后缀的长度)。
g(len)函数计算 apre(len)+bsuf(len)是否是回文。
h(len)函数： a[len…n-len-1]或 b[len…n-len-1]是否是回文。
性质一：如果g(len)不成立，则一定不是回文。
性质二：如果len2 > len1，g(len)不成立，则g(len2)一定不成立。
推论一：当g(len)不成立，不需要判断更大的len。
性质三：len1 <len2，g(len1)和g(len2)成立,h(len1)成立。则：h(len2)也成立。
h(len2)涉及的子串比h(len1)短，且中心相同。
推论二：只需要判断f(len)成立的最大len。
两层循环，时间复杂度都是O(n)。

代码

核心代码

class Solution {public:bool checkPalindromeFormation(string a, string b) {auto h = [&](const string& str,int len) {for (int i = len; i < a.length()/2; i++){if (str[i] != str[a.length() - 1 - i]) {return false; }}return true;};auto f = [&](string a, string b) {for (int i = 0; i < a.length() / 2; i++){if (a[i] != b[a.length() - 1 - i]) { return h(a,i)||h(b,i); }}return true;};return f(a, b) || f(b, a);}};

单元测试

string a,b;TEST_METHOD(TestMethod11){a = "x", b = "y";auto res = Solution().checkPalindromeFormation(a, b);AssertEx(true, res);}TEST_METHOD(TestMethod12){a = "xbdef", b = "xecab";auto res = Solution().checkPalindromeFormation(a, b);AssertEx(false, res);}TEST_METHOD(TestMethod13){a = "ulacfd", b = "jizalu";auto res = Solution().checkPalindromeFormation(a, b);AssertEx(true, res);}TEST_METHOD(TestMethod14){a = "aejbaalflrmkswrydwdkdwdyrwskmrlfqizjezd", b = "uvebspqckawkhbrtlqwblfwzfptanhiglaabjea";auto res = Solution().checkPalindromeFormation(a, b);AssertEx(true, 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++**实现。