本文涉及知识点
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 <= 105
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);
}