LeetCode 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 <= 105a.length == b.lengtha和b都只包含小写英文字母
方法一：双指针
假设我们取了aprefixa_{prefix}aprefix和bsuffixb_{suffix}bsuffix，并且组成了newStrnewStrnewStr，那么newStrnewStrnewStr由三部分构成：
newStr=s1+s2+s3newStr = s_1 + s_2 + s_3newStr=s1+s2+s3，且s1∈aprefixs_1\in a_{prefix}s1∈aprefix，s3∈bsuffixs_3 \in b_{suffix}s3∈bsuffix，s1s_1s1和s3s_3s3互为回文串，s2s_2s2自身为回文串。
举个例子：
a = “abkfkzz”, b = “xxiouba”
我们令aprefix=abkfka_{prefix} = abkfkaprefix=abkfk，令bsuffix=bab_{suffix} = babsuffix=ba，则newStr=abkfkbanewStr = abkfkbanewStr=abkfkba
newStrnewStrnewStr由三部分组成：abkfkba=ab+kfk+baabkfkba = ab + kfk + baabkfkba=ab+kfk+ba
其中s1=ab∈aperfixs_1 = ab \in a_{perfix}s1=ab∈aperfix，s3=ba∈bsuffixs_3 = ba \in b_{suffix}s3=ba∈bsuffix，ababab和bababa互为回文串，s2=kfks_2 = kfks2=kfk自身为回文串。
那么思路来了：
一个指针指向aaa串的首部，另一个指针指向bbb串的尾部，当两个指针所指字符相等时，a指针后移b指针前移，直到两指针相遇或两指针所指不同为止。
- 如果两指针相遇，则说明aperfixa_{perfix}aperfix和bsuffixb_{suffix}bsuffix已经互为回文，s2s_2s2为空即可，直接返回truetruetrue
- 如果两指针所指不同，则a指针前面的部分视为s1s_1s1，b指针后面的部分视为s3s_3s3（可以保证s1s_1s1和s3s_3s3互为回文），字符串a或字符串b 从a指针到b指针的部分 视为s2s_2s2，只需要判断s2s_2s2自身是否为回文串即可。若是则返回true，不是则返回false
上面判断了aperfix+bsuffixa_{perfix} + b_{suffix}aperfix+bsuffix的情况，bperfix+asuffixb_{perfix} + a_{suffix}bperfix+asuffix则同理
- 时间复杂度O(len(a))O(len(a))O(len(a))
- 空间复杂度O(1)O(1)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 Falsel += 1r -= 1return Truedef ifOk(self, a: str, b: str) -> bool:la = 0lb = len(b) - 1while la < lb:if a[la] != b[lb]:if self.ifSelfPalindrome(a, la, lb) or self.ifSelfPalindrome(b, la, lb):return Trueelse:return Falsela += 1lb -= 1return Truedef 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