Medium

题目描述

给你两个长度相同的字符串 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 = "xbdef", b = "xecab"
输出：false

示例 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 <= 10^5
  • a.length == b.length
  • a 和 b 由小写英文字母组成

解题思路

这道题需要检查是否可以通过在相同位置分割两个字符串，然后交叉组合形成回文串。

核心思路： 我们需要检查两种组合：aprefix + bsuffix 和 bprefix + asuffix 是否能形成回文串。

关键观察：

  1. 如果 aprefix + bsuffix 是回文串，那么从两端开始匹配时，要么 a[i] == b[n-1-i] 继续匹配，要么在某个位置停下来检查剩余部分。
  2. 当外层匹配停止时，剩余的中间部分必须是回文串，这部分要么全来自字符串 a，要么全来自字符串 b。

算法步骤：

  1. 定义辅助函数 check(s1, s2)：检查是否可以用 s1 的前缀 + s2 的后缀形成回文串
  2. 在 check 函数中：
    • 使用双指针从两端开始匹配 s1[i] 和 s2[j]
    • 当匹配失败时，检查剩余部分：s1[i...j] 或 s2[i...j] 是否为回文串
  3. 最终结果是 check(a, b) || check(b, a)

这种方法的优势是避免了枚举所有分割点，而是通过双指针直接找到关键的分割位置。

代码实现

class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        return check(a, b) || check(b, a);
    }
    
private:
    bool check(const string& s1, const string& s2) {
        int i = 0, j = s1.length() - 1;
        
        // 从两端开始匹配
        while (i < j && s1[i] == s2[j]) {
            i++;
            j--;
        }
        
        // 检查剩余部分是否为回文串
        return isPalindrome(s1, i, j) || isPalindrome(s2, i, j);
    }
    
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def check(s1, s2):
            i, j = 0, len(s1) - 1
            
            # 从两端开始匹配
            while i < j and s1[i] == s2[j]:
                i += 1
                j -= 1
            
            # 检查剩余部分是否为回文串
            return is_palindrome(s1, i, j) or is_palindrome(s2, i, j)
        
        def is_palindrome(s, left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
        
        return check(a, b) or check(b, a)

public class Solution {
    public bool CheckPalindromeFormation(string a, string b) {
        return Check(a, b) || Check(b, a);
    }
    
    private bool Check(string s1, string s2) {
        int i = 0, j = s1.Length - 1;
        
        // 从两端开始匹配
        while (i < j && s1[i] == s2[j]) {
            i++;
            j--;
        }
        
        // 检查剩余部分是否为回文串
        return IsPalindrome(s1, i, j) || IsPalindrome(s2, i, j);
    }
    
    private bool IsPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

var checkPalindromeFormation = function(a, b) {
    const check = (s1, s2) => {
        let i = 0, j = s1.length - 1;
        
        // 从两端开始匹配
        while (i < j && s1[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)每次检查最多遍历字符串一次，总共检查两次
空间复杂度O(1)只使用常数额外空间