题目描述

给定两个字符串 a 和 b，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串：a_prefix 和 a_suffix，满足 a = a_prefix + a_suffix，同理，由 b 可以得到两个字符串 b_prefix 和 b_suffix，满足 b = b_prefix + b_suffix。请你判断 a_prefix + b_suffix 或者 b_prefix + a_suffix 能否构成回文串。

当你将一个字符串 s 分割成 s_prefix 和 s_suffix 时，s_suffix 或者 s_prefix 可以为空。比方说，s = "abc" 那么 "" + "abc"，"a" + "bc"，"ab" + "c" 和 "abc" + "" 都是合法分割。

如果 能构成回文字符串，那么请返回 true，否则返回 false。

请注意，x + y 表示连接字符串 x 和 y。

样例

输入：a = "x", b = "y"
输出：true
解释：如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割：
a_prefix = "", a_suffix = "x"
b_prefix = "", b_suffix = "y"
那么 a_prefix + b_suffix = "" + "y" = "y" 是回文串。

输入：a = "ulacfd", b = "jizalu"
输出：true
解释：在下标为 3 处分割：
a_prefix = "ula", a_suffix = "cfd"
b_prefix = "jiz", b_suffix = "alu"
那么 a_prefix + b_suffix = "ula" + "alu" = "ulaalu" 是回文串。

限制

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

算法

(分情况讨论) $O(n)$

1. 不妨只枚举 a 的前缀与 b 的后缀拼接产生回文串的情况。因为 a 的后缀与 b 的前缀可以通过交换 a 和 b 的方式得到。
2. a 的前缀与 b 的后缀拼接又可以分为两类，以 a 的前缀为基准产生回文串，和以 b 的后缀为基准产生回文串。不妨只考虑以 a 的前缀为基准，和 b 的后缀拼接产生回文串的情况。因为后者可以通过翻转 a 和 b 字符串再交换得到。
3. 以 a 的前缀为基准产生回文串时，我们可以参考如何判断一个字符串是否回文。在判断过程中，优先判断 a[i] 是否等于 b[j]。如果 a[i] 不等于 b[j]，则再判断 a[i] 与 a[j] 的关系，且之后都必须只能通过 a[i] 与 a[j] 来判断。

时间复杂度

• 共四种情况，每种情况遍历字符串一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    bool judge(const string &first, const string &second) {
        const int len = first.size();
        bool mustUseFirst = false;
        for (int i = 0, j = len - 1; i < j; i++, j--) {
            if (mustUseFirst) {
                if (first[i] != first[j]) return false;
            } else {
                if (first[i] != second[j]) {
                    if (first[i] != first[j]) return false;
                    mustUseFirst = true;
                }
            }
        }
        return true;
    }

public:
    bool checkPalindromeFormation(string a, string b) {
        if (judge(a, b) || judge(b, a))
            return true;

        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        return judge(a, b) || judge(b, a);
    }
};