Leetcode 1616. Split Two Strings to Make Palindrome

题目：解法1：暴力，TLE解法2：O(n)

题目：

解法1：暴力，TLE

class Solution: def checkPalindromeFormation(self, a: str, b: str) -> bool: if len(a) == 1 or len(b) == 1: return True n = len(a) if a[0]!=b[-1] and b[0]!=a[-1]: return False def check(string): l = 0 r = len(string)-1 while l<=r: if string[l]!=string[r]: return False l+=1 r-=1 return True for 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 True return 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 = 0 r = len(string)-1 while l<=r: if string[l]!=string[r]: return False l+=1 r-=1 return True def check2(a,b): l = 0 r = n-1 while l<r and a[l]==b[r]: l += 1 r -= 1 return 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，判断是否能构成回文