Editorial: LeetCode 1616 Split Two Strings to Make Palindrome
https://leetcode.com/problems/split-two-strings-to-make-palindrome/ from Google
Thinking process:
We need to find the palindrome by using A.prefix + B.suffix or B.prefix + A.suffix. To find this, we can check if A[0] == B[-1], if yes, we can check if A[1] == B[-2], and so on. Keep going until they are not the same. Like below, we can see that A[3] != B[-4]. Now, we can either split at A[3] or B[-4]. If we split at A[3], ?????d must be a palindrome. If we split at B[-4], a????? must be a palindrome.
abc a????? xxx
yyy ?????d cba
The above case is for A.prefix + B.suffix, and we can do the same thing for B.prefix + A.suffix as well. The only thing left is: we split at A[0] or B[0], which means the answer is true if either A itself or B itself is a palindrome, so we just need to add this special case.
1class Solution {
2public:
3 bool is(string s) {
4 int N = s.size();
5 int l=0, r=N-1;
6 while (l<r) {
7 if (s[l]!=s[r]) return false;
8 l++, r--;
9 }
10 return true;
11 }
12 bool checkPalindromeFormation(string a, string b) {
13 if (is(a) or is(b)) return true;
14 int N = a.size();
15 int l=0, r=N-1;
16 bool checkA = true, checkB = true;
17 while (l<r and (checkA or checkB)) {
18 if (a[l] == b[r] and b[l] == a[r]) {
19 // nop
20 }
21 if (checkA and a[l] != b[r]) {
22 checkA = false;
23 if (is(a.substr(l, r-l+1)) or is(b.substr(l, r-l+1))) return true;
24 }
25 if (checkB and b[l] != a[r]) {
26 checkB = false;
27 if (is(a.substr(l, r-l+1)) or is(b.substr(l, r-l+1))) return true;
28 }
29 l++, r--;
30 }
31 return checkA or checkB;
32 }
33};