分割两个字符串得到回文串

标签: 双指针 字符串

难度: 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 = "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 <= 105
  • a.length == b.length
  • a 和 b 都只包含小写英文字母

Submission

运行时间: 54 ms

内存: 16.6 MB

import random
class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def check(a, b):
            i = 0
            j = len(a) - 1
            while i < j and a[i] == b[j]:
                i += 1
                j -= 1
            x = a[i : j + 1]
            h = b[i : j + 1]
            return x == x[::-1] or h == h[::-1]
        return check(a, b) or check(b, a)

Explain

The solution first defines a helper function `check(a, b)` that checks if `a` and `b` can form a palindrome by splitting at the same index. It starts by comparing characters from the outer edges towards the center. If the characters at positions `i` and `j` are the same, it moves inward. When it encounters characters that don't match, it takes the substring from `i` to `j` (inclusive) from both strings and checks if either substring is a palindrome. If either is a palindrome, it means a palindrome can be formed by combining the prefixes and suffixes of `a` and `b`. The main function calls `check(a, b)` and `check(b, a)` to cover both possibilities of forming a palindrome and returns `true` if either call returns `true`.

时间复杂度: O(n)

空间复杂度: O(n)

import random
class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def check(a, b):
            i = 0
            j = len(a) - 1
            while i < j and a[i] == b[j]:
                i += 1
                j -= 1
            x = a[i : j + 1]
            h = b[i : j + 1]
            return x == x[::-1] or h == h[::-1]
        return check(a, b) or check(b, a)

Explore

在i和j处的字符相同时，继续移动指针i和j是为了尽可能地从外部向中心检查两个字符串的字符是否匹配，这样可以最大化地使用两个字符串的相同部分来形成可能的回文结构。这种方法是高效的，因为它避免了在每个步骤中进行不必要的回文检查，只有在遇到第一个不匹配的字符时才进行回文检查，从而减少了计算量。

`check(a, b)`函数检查是否可以通过在某些点将字符串a和b分割后，用a的前缀和b的后缀组合成一个回文串。相反，`check(b, a)`检查是否可以用b的前缀和a的后缀组合成一个回文串。这两个函数调用确保了无论回文是从字符串a的前缀开始还是从字符串b的前缀开始的情况都被考虑到了，这样可以全面地检查两个字符串的任何组合方式是否能形成回文串。

当在两个字符串中找到第一个不匹配的字符对时，只需检查剩余的子串是否为回文，因为如果剩余子串是回文，就意味着可以通过连接已匹配的前缀和后缀形成一个完整的回文串。这种方法基于回文的对称性质，确保了不会遗漏其他可能性，因为任何更长的非匹配部分都会破坏整体的回文结构。

对于长度为1或特别短的字符串，算法自然会处理这些情况，因为循环条件`i < j`会很快不成立，从而使得整个字符串或其大部分直接进入回文检查。例如，如果字符串长度为1，那么在`check(a, b)`函数中，循环可能根本不执行，直接返回`true`，因为长度为1的任何字符串都是回文。因此，算法设计已经包含了处理这类边界情况的逻辑。