class Solution {
public:
bool checkPalindromeFormation(string a, string b) {
}
};
1616. 分割两个字符串得到回文串
给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： aprefix 和 asuffix ，满足 a = aprefix + asuffix ，同理，由 b 可以得到两个字符串 bprefix 和 bsuffix ，满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。
当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix 可以为空。比方说， s = "abc" 那么 "" + "abc" ， "a" + "bc" ， "ab" + "c" 和 "abc" + "" 都是合法分割。
如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
注意， x + y 表示连接字符串 x 和 y 。
示例 1：
输入：a = "x", b = "y" 输出：true 解释：如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割： aprefix = "", asuffix = "x" bprefix = "", bsuffix = "y" 那么 aprefix + bsuffix = "" + "y" = "y" 是回文串。
示例 2：
输入：a = "abdef", b = "fecab" 输出：true
示例 3：
输入：a = "ulacfd", b = "jizalu" 输出：true 解释：在下标为 3 处分割： aprefix = "ula", asuffix = "cfd" bprefix = "jiz", bsuffix = "alu" 那么 aprefix + bsuffix = "ula" + "alu" = "ulaalu" 是回文串。
提示：
1 <= a.length, b.length <= 105a.length == b.lengtha 和 b 都只包含小写英文字母原站题解
cpp 解法, 执行用时: 48 ms, 内存消耗: 35.5 MB, 提交时间: 2023-03-18 08:49:39
class Solution {
bool check(string a, string b) {
int n = a.size();
bool flag = true;
for (int i = 0; i < n / 2; ++i) {
if (flag) {
if (a[i] != b[n - 1 - i])
flag = false;
}
if (!flag)
if (a[i] != a[n - 1 - i])
return false;
}
return true;
}
public:
bool checkPalindromeFormation(string a, string b) {
if (check(a, b) || check(b, a))
return true;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
if (check(a, b) || check(b, a))
return true;
return false;
}
};
javascript 解法, 执行用时: 72 ms, 内存消耗: 48.6 MB, 提交时间: 2023-03-18 08:49:21
/**
* @param {string} a
* @param {string} b
* @return {boolean}
*/
var checkPalindromeFormation = function(a, b) {
return checkConcatenation(a, b) || checkConcatenation(b, a);
}
const checkConcatenation = (a, b) => {
const n = a.length;
let left = 0, right = n - 1;
while (left < right && a[left] === b[right]) {
left++;
right--;
}
if (left >= right) {
return true;
}
return checkSelfPalindrome(a, left, right) || checkSelfPalindrome(b, left, right);
}
const checkSelfPalindrome = (a, left, right) => {
while (left < right && a[left] === a[right]) {
left++;
right--;
}
return left >= right;
};
golang 解法, 执行用时: 20 ms, 内存消耗: 6.6 MB, 提交时间: 2023-03-18 08:48:57
func checkPalindromeFormation(a, b string) bool {
return checkConcatenation(a, b) || checkConcatenation(b, a)
}
func checkConcatenation(a, b string) bool {
left, right := 0, len(a)-1
for left < right && a[left] == b[right] {
left++
right--
}
if left >= right {
return true
}
return checkSelfPalindrome(a[left:right+1]) || checkSelfPalindrome(b[left:right+1])
}
func checkSelfPalindrome(s string) bool {
left, right := 0, len(s)-1
for left < right && s[left] == s[right] {
left++
right--
}
return left >= right
}
java 解法, 执行用时: 3 ms, 内存消耗: 42.3 MB, 提交时间: 2023-03-18 08:48:43
class Solution {
public boolean checkPalindromeFormation(String a, String b) {
return checkConcatenation(a, b) || checkConcatenation(b, a);
}
public boolean checkConcatenation(String a, String b) {
int n = a.length();
int left = 0, right = n - 1;
while (left < right && a.charAt(left) == b.charAt(right)) {
left++;
right--;
}
if (left >= right) {
return true;
}
return checkSelfPalindrome(a, left, right) || checkSelfPalindrome(b, left, right);
}
public boolean checkSelfPalindrome(String a, int left, int right) {
while (left < right && a.charAt(left) == a.charAt(right)) {
left++;
right--;
}
return left >= right;
}
}
python3 解法, 执行用时: 96 ms, 内存消耗: 15.8 MB, 提交时间: 2023-03-18 08:48:22
class Solution:
def checkPalindromeFormation(self, a: str, b: str) -> bool:
return self.checkConcatenation(a, b) or self.checkConcatenation(b, a)
def checkConcatenation(self, a: str, b: str) -> bool:
n = len(a)
left, right = 0, n-1
while left < right and a[left] == b[right]:
left += 1
right -= 1
if left >= right:
return True
return self.checkSelfPalindrome(a, left, right) or self.checkSelfPalindrome(b, left, right)
def checkSelfPalindrome(self, a: str, left: int, right: int) -> bool:
while left < right and a[left] == a[right]:
left += 1
right -= 1
return left >= right