题目链接：1616. 分割两个字符串得到回文串
方法：模拟 + 双指针
解题思路
- 题目要求，找一个合适的下标 \(idx\) 将 \(a\) 分割为 \(a[0, idx]\) 和 \(a[idx + 1, n - 1]\)，同样的 \(b\) 分割为 \(b[0, idx]\) 和 \(b[idx + 1, n - 1]\)，然后使得 \(a[0, idx] + b[idx + 1, n - 1]\) 或 \(b[0, idx] + a[idx + 1, n - 1]\) 为回文字符串，若存在下标 \(idx\)，则返回
true，否则返回false。 - 若是 \(a[0, idx] + b[idx + 1, n - 1]\) 为回文串，则从左→右遍历 \(a\)，从右←左遍历 \(b\)，判断是否可能存在回文串；同理若是 \(b[0, idx] + a[idx + 1, n - 1]\)为回文字符串，则改变遍历方向，从左→右遍历 \(b\)，从右←左遍历 \(a\)，判断是否可能存在回文串；
- 实际上上述的两个过程是相同的，那么可以写成一个函数形式 \(check()\)，在传参数时分别为 \(check(a, b)\) 和 \(check(b, a)\) 即对应上述两种过程。
- 如何检查上述情况是否存在？
对于 \(check(a, b)\)：初始化 \(l = 0, r = n - 1\)，从左→右遍历 \(a\)，从右←左遍历 \(b\)，当 \(a[l] != b[r]\) 时，检查 \(a[l, r]\) 或 \(b[l, r]\) 是否为回文串，若有一个则返回true，假设是 \(a[l, r]\) 为回文串，则 \(a[0, l - 1] + a[l, r] + b[r + 1, n - 1]\) 构成回文串，此时 \(idx = r\)。
代码
// 优化后代码
class Solution {
public:
bool checkPalindrome(string str) {
int n = str.length();
for (int i = 0; i < n / 2; i ++ ) {
if (str[i] != str[n - i - 1]) {
return false;
}
}
return true;
}
bool check(string a, string b) {
int n = a.length();
int l = 0, r = n - 1;
while (l < r) {
if (a[l] == b[r]) {
l ++ ;
r --;
} else {
break;
}
}
if (checkPalindrome(a.substr(l, r - l + 1)) || checkPalindrome(b.substr(l, r - l + 1))) return true;
return false;
}
bool checkPalindromeFormation(string a, string b) {
// 从左→右遍历a，从右←左遍历b，判断是否可能存在回文串
// 改变遍历方向，从左→右遍历b，从右←左遍历a，判断是否可能存在回文串
return check(a, b) || check(b, a);
}
};
// 优化前代码
class Solution {
public:
bool checkPalindromeFormation(string a, string b) {
int n = a.length();
// a 和 b有一个为回文串，则返回true
int flag1 = true, flag2 = true;
for (int i = 0; i <= n / 2; i ++ ) {
if (a[i] != a[n - i - 1]) {
flag1 = false;
}
if (b[i] != b[n - i - 1]) {
flag2 = false;
}
}
if (flag1 || flag2) return true;
// 从左→右遍历a，从右←左遍历b，判断是否可能存在回文串
int l = 0, r = n - 1;
while (l < r) {
if (a[l] == b[r]) {
l ++ ;
r --;
} else {
break;
}
}
if (r == l - 1 || r == l) return true; // 说明左右指针相遇，即可以在此截断，此时a[0, l - 1] + b[l, n - 1]为回文串，此时分开下标为l - 1。
else if (r - l + 1 != n) { // 否则表明左右指针未相遇，在继续判断a[l, r] 或 b[l, r]是否为回文串，假设a[l, r]为回文串，则a[0, r] + b[r + 1, n - 1]为回文串，此时分开下标为r。
int left = l, right = r;
while (left < right) {
if (a[left] == a[right]) {
left ++ ;
right -- ;
} else {
break;
}
}
if (left - 1 == right || left == right) return true;
left = l, right = r;
while (left < right) {
if (b[left] == b[right]) {
left ++ ;
right -- ;
} else {
break;
}
}
if (left - 1 == right || left == right) return true;
}
// 同上，改变遍历方向，从左→右遍历b，从右←左遍历a，判断是否可能存在回文串
l = 0, r = n - 1;
while (l < r) {
if (b[l] == a[r]) {
l ++ ;
r --;
} else {
break;
}
}
if (r == l - 1 || r == l) return true;
else if (r - l + 1 != n) {
int left = l, right = r;
while (left < right) {
if (a[left] == a[right]) {
left ++ ;
right -- ;
} else {
break;
}
}
if (left - 1 == right || left == right) return true;
left = l, right = r;
while (left < right) {
if (b[left] == b[right]) {
left ++ ;
right -- ;
} else {
break;
}
}
if (left - 1 == right || left == right) return true;
}
return false;
}
};
复杂度分析
时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。