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

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

题目描述：

给出两个长度为 $n$ 的字符串。选择一个下标，将两个字符串在这个位置分割开，得到 $a_{prefix}$ 和 $a_{suffix}$ ，以及 $b_{prefix}$ 和 $b_{subfix}$ 。判断 $a_{prefix} + b_{subfix}$ 或 $b_{prefix} + a_{subfix}$ 能否构成回文串。注意空字符串也是合法分割。

数据范围：
$1\le n \le 10^5$

题解：

首先写一个检测字符串 $[left, right]$ 是否是回文串的函数。同时 $a_{prefix} + b_{subfix}$ 或 $b_{prefix} + a_{subfix}$ 也是两个相同的问题，只需要判断一个，然后交换 $a$ 和 $b$ 再调用一次。

首先使用双指针 $left,right$ 判断 $a[left]$ 的前缀和 $b[right]$ 的后缀是否相等，不相等时，判断 $a[left, right], b[left, right]$ 是否是回文串即可。

代码：

class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    bool isPalindrome(string &s, int left, int right)
    {
        while (left < right)
        {
            if (s[left] != s[right])
            {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    bool check(string &a, string &b)
    {
        int left = 0, right = b.size() - 1;
        while (left < right && a[left] == b[right])
        {
            left++;
            right--;
        }
        if (left == right)
            return true;
        if (isPalindrome(b, left, right) || isPalindrome(a, left, right))
        {
            return true;
        }
        return false;
    }
    bool checkPalindromeFormation(string a, string b)
    {
        return check(a, b) || check(b, a);
    }
};