原文链接: https://leetcode-cn.com/problems/split-two-strings-to-make-palindrome

英文原文

You are given two strings a and b of the same length. Choose an index and split both strings at the same index, splitting a into two strings: aprefix and asuffix where a = aprefix + asuffix, and splitting b into two strings: bprefix and bsuffix where b = bprefix + bsuffix. Check if aprefix + bsuffix or bprefix + asuffix forms a palindrome.

When you split a string s into sprefix and ssuffix, either ssuffix or sprefix is allowed to be empty. For example, if s = "abc", then "" + "abc", "a" + "bc", "ab" + "c" , and "abc" + "" are valid splits.

Return true if it is possible to form a palindrome string, otherwise return false.

Notice that x + y denotes the concatenation of strings x and y.

 

Example 1:

Input: a = "x", b = "y"
Output: true
Explaination: If either a or b are palindromes the answer is true since you can split in the following way:
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
Then, aprefix + bsuffix = "" + "y" = "y", which is a palindrome.

Example 2:

Input: a = "abdef", b = "fecab"
Output: true

Example 3:

Input: a = "ulacfd", b = "jizalu"
Output: true
Explaination: Split them at index 3:
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
Then, aprefix + bsuffix = "ula" + "alu" = "ulaalu", which is a palindrome.

Example 4:

Input: a = "xbdef", b = "xecab"
Output: false

 

Constraints:

• 1 <= a.length, b.length <= 105
• a.length == b.length
• a and b consist of lowercase English letters

中文题目

给你两个字符串 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" 是回文串。

示例 4：

输入：a = "xbdef", b = "xecab"
输出：false

 

提示：

• 1 <= a.length, b.length <= 105
• a.length == b.length
• a 和 b 都只包含小写英文字母

通过代码

高赞题解

思路

1. 题目给出的字符串长度固定，可以直接使用 中心扩展法 检测

   1. 由中心向两侧分别检测字符串 a 和 b
   2. 即【前 a 后 a】和【前 b 后 b】
   3. 不断扩展，直到字符不相同，中间部分都是回文串
   4. 结合下图观看，同时检测两条字符串，我们只关心回文更长的那串，具体是哪条更长不重要

2. 当不符合回文串时，有一次机会将两个字符串拼接一下

   1. 继续扩展检测，这次检测拼接后的字符串
   2. 即【前 a 后 b】和【前 b 后 a】
   3. 结合下图观看，因为拼接的字符串既有 a 也有 b，所以之前更长的是哪串都不影响

3. 当再次结束检测时

   1. 如字符再次不相同，则是匹配失败
   2. 如全部匹配，则 left 应该为 -1

图解

• 如图所示，第一次检测时，字符串 a 的中心并没有回文串，而字符串 b 有一段合法回文串
• 第二次检测时，【前 a 后 b】通过测试
• 最终，【前 a 后 b】和 b 的中心子串组合起来，就是拼接后的回文串（所有有底色的字符）

答题

[]
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        int left = a.size() / 2 - 1;
        left = min(check(a, a, left), check(b, b, left));
        left = min(check(a, b, left), check(b, a, left));
        return left == -1;
    }

    int check(string str_l, string str_r, int left) {
        int right = str_l.size() - 1 - left;
        while (left >= 0 && right < str_l.size()) {
            if (str_l[left] != str_r[right]) break;
            left--;
            right++;
        }
        return left;
    }
};

致谢

感谢您的观看，希望对您有帮助，欢迎热烈的交流！

如果感觉还不错就点个赞吧~

这是 我的leetcode ，帮助我收集整理题目，可以方便的 visual studio 调试，欢迎关注，star。

统计信息

通过次数	提交次数	AC比率
5180	18737	27.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言