Leetcode 1616. Split Two Strings to Make Palindrome (python+cpp)

题目：

解法1：暴力，TLE

class Solution:def checkPalindromeFormation(self, a: str, b: str) -> bool:if len(a) == 1 or len(b) == 1:return Truen = len(a)if a[0]!=b[-1] and b[0]!=a[-1]:return Falsedef check(string):l = 0r = len(string)-1while l<=r:if string[l]!=string[r]:return Falsel+=1r-=1return Truefor i in range(n):new_str1 = a[:i] + b[i:]new_str2 = b[:i]+a[i:]if check(new_str1) or check(new_str2):return Truereturn False

这边顺便说说TLE的问题，对于leetcode，一般我们需要假设case能在1秒内跑完，正常cpu每秒1亿次运算。对这道题，字符串长度在100000，如果暴力做，每个字符串反转比较还要花同样的同样的时间，总的就需要10的10次，也就是10秒，肯定超时

解法2：O(n)

以a取prefix和b取suffix为例。双指针法，a从头开始，b从未开始，刚开始的若干个字符一定是相等的，找出第一次不能的left和right的位置，由于两个子串加起来一定等于原来长度，而且之前的位置确保回文，那么现在只需要满足a和b中left到right的位置也是回文即可。两边比较过的字符，加上left-right的字符加起来一定刚好等于原来字符的长度。

这种咋说呢，一开始没有想到还是因为太笨了，观察不够仔细，没有想到题目的本质是a，b分别取头和尾，然后取a或者b中头尾位置之间的回文串组成总的回文串

class Solution:def checkPalindromeFormation(self, a: str, b: str) -> bool:n = len(a)def check1(string):l = 0r = len(string)-1while l<=r:if string[l]!=string[r]:return Falsel+=1r-=1return Truedef check2(a,b):l = 0r = n-1while l<r and a[l]==b[r]:l += 1r -= 1return check1(a[l:r+1]) or check1(b[l:r+1])return check2(a,b) or check2(b,a)

check1检查给定字符串是否回文，check2检查给定两个字符串a，b，a取prefix，b取suffix，判断是否能构成回文

二刷

几个注意点：

• 两个字符串等长
• 两个字符串必须分裂在一个位置
• 分裂后prefix或者suffix可以为空
  解题思路如下：
• 由于分裂后prefix或者suffix可以为空，那么任意一个字符串为回文就必定答案为true
• 对于其他情况有两种：1. a的prefix和b的suffix刚好对应相同且组成的串长度可以>=原串长度，例如a = “ulacfd”, b = “jizalu”；2. a的prefix和b的suffix的一部分suffix对应且b的suffix剩余的部分自己构成回文，例如a = “pvhmupgqeltozftlmfjjde”, b = "yjgpzbezspnnpszebzmhvp"或者a = “aejbaalflrmkswrydwdkdwdyrwskmrlfqizjezd”, b = “uvebspqckawkhbrtlqwblfwzfptanhiglaabjea”.

class Solution {
    
public:bool isPalin(const string& str){
    int p1 = 0;int p2 = str.size() - 1;while(p1 < p2){
    if(str[p1] != str[p2]){
    return false;}p1++;p2--;}return true;}bool helper(const string& a,const string& b){
    int p1 = 0;int p2 = b.size() - 1;while(p1 < a.size() && p2 >= 0 && a[p1] == b[p2]){
    p1++;p2--;}int num = p1 + b.size() - 1 - p2;// cout << num << " " << a << " " << b << endl;// cout << b.substr(p1,p2+1) << endl;if(num >= a.size()){
    return true;}else if(isPalin(b.substr(p1,p2-p1+1)) || isPalin(a.substr(p1,p2-p1+1))){
    return true;}return false;}bool checkPalindromeFormation(string a, string b) {
    if(isPalin(a) || isPalin(b)) {
    return true;}if(helper(a,b)) return true;if(helper(b,a)) return true;return false;}
};