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

【LetMeFly】1616.分割两个字符串得到回文串

力扣题目链接：https://leetcode.cn/problems/split-two-strings-to-make-palindrome/

给你两个字符串 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 都只包含小写英文字母

方法一：双指针

假设我们取了$a_{prefix}$和$b_{suffix}$，并且组成了$newStr$，那么$newStr$由三部分构成：

$newStr = s_1 + s_2 + s_3$，且$s_1\in a_{prefix}$，$s_3 \in b_{suffix}$，$s_1$和$s_3$互为回文串，$s_2$自身为回文串。

举个例子：

a = “abkfkzz”, b = “xxiouba”

我们令$a_{prefix} = abkfk$，令$b_{suffix} = ba$，则$newStr = abkfkba$

$newStr$由三部分组成：$abkfkba = ab + kfk + ba$

其中$s_1 = ab \in a_{perfix}$，$s_3 = ba \in b_{suffix}$，$ab$和$ba$互为回文串，$s_2 = kfk$自身为回文串。

那么思路来了：

一个指针指向$a$串的首部，另一个指针指向$b$串的尾部，当两个指针所指字符相等时，a指针后移b指针前移，直到两指针相遇或两指针所指不同为止。

• 如果两指针相遇，则说明$a_{perfix}$和$b_{suffix}$已经互为回文，$s_2$为空即可，直接返回$true$
• 如果两指针所指不同，则a指针前面的部分视为$s_1$，b指针后面的部分视为$s_3$（可以保证$s_1$和$s_3$互为回文），字符串a或字符串b 从a指针到b指针的部分 视为$s_2$，只需要判断$s_2$自身是否为回文串即可。若是则返回true，不是则返回false

上面判断了$a_{perfix} + b_{suffix}$的情况，$b_{perfix} + a_{suffix}$则同理

• 时间复杂度$O(len(a))$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
private:
    bool ifSelfPalindrome(string& s, int l, int r) {  // s[l, r]
        while (l < r) {
            if (s[l++] != s[r--]) {
                return false;
            }
        }
        return true;
    }

    bool ifOk(string& a, string& b) {
        int la = 0, lb = b.size() - 1;
        while (la < lb) {
            if (a[la] != b[lb]) {
                if (ifSelfPalindrome(a, la, lb) || ifSelfPalindrome(b, la, lb)) {
                    return true;
                }
                else {
                    return false;
                }
            }
            else {
                la++, lb--;
            }
        }
        return true;  // la和lb相遇了
    }
public:
    bool checkPalindromeFormation(string& a, string& b) {
        return ifOk(a, b) || ifOk(b, a);
    }
};

Python

class Solution:
    def ifSelfPalindrome(self, s: str, l: int, r: int) -> bool:  # s[l, r]
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

    def ifOk(self, a: str, b: str) -> bool:
        la = 0
        lb = len(b) - 1
        while la < lb:
            if a[la] != b[lb]:
                if self.ifSelfPalindrome(a, la, lb) or self.ifSelfPalindrome(b, la, lb):
                    return True
                else:
                    return False
            la += 1
            lb -= 1
        return True

    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        return self.ifOk(a, b) or self.ifOk(b, a)

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/129635845