2023-03-18 LeetCode：1616. 分割两个字符

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 。

示例

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

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

解题思路

核心思路：双指针

1. 用两个指针left、right分别遍历a、b两个字符串，如果相等， 继续比较下一个字符；如果两个指针相遇，表示可以构成回文字符串；
2. 如果两个指针没有相遇，仍有可能构成回文字符串，例如：

a = "axxx", b = "bvva".  a + vva

当指针left到x、指针right到v时比较失败，
我们此时可以组成avva、bxxx，用双指针的办法判断这两个字符串是否是回文字符串即可。

代码示例（JAVA）

class Solution {
    public boolean checkPalindromeFormation(String a, String b) {
        return checkStrings(a, b) || checkStrings(b, a);
    }

    public boolean checkStrings(String a, String b) {
        int length = a.length();
        int left = 0, right = length - 1;
        while (a.charAt(left) == b.charAt(right) && left < right) {
            left++;
            right--;
        }
        // 有一半相同，肯定是，例如：a = "ulacfd", b = "jizalu"
        if (left >= right) {
            return true;
        }
        // a = "axxx", b = "bvva" a + vva
        return checkString(a, left, right) || checkString(b, left, right);
    }

    public boolean checkString(String a, int left, int right) {
        while (left < right && a.charAt(left) == a.charAt(right)) {
            left++;
            right--;
        }
        if (left >= right) {
            return true;
        }
        return false;
    }
}

时间复杂度：O(n)