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

难度

• Easy
• Medium
• Hard

思路

首先想到枚举分割点直接判断，但取子串和取反的操作会导致超时。

从最长逆序长度考虑。

先将 a 和 b 分别作为 s1 s2 来考虑。

初始 break_point = -1

两指针分别从 s1 的首部，s2 的尾部出发，字符相同则更新 break_point 并前进，不同则终止。

此时 break_point 只有三种情况：

1. 等于 -1 ，说明不行。
2. 大于等于 s1 长度的一半，说明可以。
3. 大于 -1 且小于 s1 长度的一半，需要进一步判断。此时已经可以确定生成的回文串的首尾，只要确定其中间部分。中间部分可以取 s1 的中间，也可以取 s2 的中间，任意一种成立均可以。两种都不成立则说明不行。

以上任意一种情况成立时返回 True

否则最终返回 False。

代码

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        if a == a[::-1] or b == b[::-1]:
            return True

        def check(s1: str, s2:str) -> bool:
            n = len(s1)

            # 计算相同长度
            break_point = -1
            for idx in range(n):
                if s2[idx] == s1[-1 - idx]:
                    break_point = idx
                else:
                    break

            # 相同长度短于一半
            if -1 < break_point < (n - 1) // 2:
                surplus_1 = s1[break_point + 1:n - 1 - break_point]
                surplus_2 = s2[break_point + 1:n - 1 - break_point]
                if surplus_1 == surplus_1[::-1] or surplus_2 == surplus_2[::-1]:
                    return True
            # 相同长度长于一半
            elif break_point >= (n - 1) // 2:
                return True

            return False

        return check(a, b) or check(b, a)

时间超过 95% ，空间超过 70%。