题目描述：
给出两个长度为 $ 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] $ 是否是回文串即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| 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);
}
};
|