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

发表于 分类于 阅读次数：

前言

题目来自LeetCode：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：

1
2
3
4
5
6
输入：a = "abdef", b = "fecab"
输出：true
解释：
aprefix = "abd", asuffix = "ef"
bprefix = "fec", bsuffix = "ab"
那么 bprefix + asuffix = "fec" + "ef" = "fecef" 是回文串。

提示：

  • 1 <= a.length, b.length <= 10^5
  • a.length == b.length
  • a 和 b 都只包含小写英文字母

题解

首先，回顾单字符串如何判断其是否是回文串，只需要使用双指针，分别指向一头一尾，判断两个指针所指的字符是否相等，若相等则两个指针往中间靠，直到两个指针相遇或交叉时，之前的判断都成立，那么这个字符串则是回文串。
此题就是回文字符串的延申，在某处切割字符串会形成4个新的字符串：aprefix,asuffix,bprefix,bsuffix，而新字符串只能是aprefix + bsuffix或则bprefix + asuffix。那么先考虑第一种情况：aprefix + bsuffix。
示例
既然是a串前面加上b串后面，那么新串要是回文串，那就可以用判断单串的方法设两个指针，一个在a串的前头，一个在b串的后头，当判断到不相等的时候，如图所示竖线位置，进一步将字符串分成6段，因为当前只考虑第一种情况，所以3，4不需要考虑，当2，5其中一个为回文串的时候，一定能找到一个切位使得第一种情况为回文串。若2为回文串，则在2的末端作为切点，若5为回文串，则在1的结尾作为切点，若2，5都不是回文串，那么第一种情况则无法形成回文串。第二种情况，实则就是将a串和b串调换位置，方法是一致的。

代码 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public boolean checkPalindromeFormation(String a, String b) {
        //第一种情况和第二种情况
        return check(a, b) || check(b,a);
    }

    public boolean check(String a, String b){
        int i = 0;
        int j = b.length() - 1;
        while(j >= 0){
            //找到竖线所在的位置
            if(a.charAt(i) != b.charAt(j)){
                break;
            }
            i++;
            j--;
        }
        //检查2，5是否为回文串
        return checkMid(a, i, j) || checkMid(b, i, j);
    }

    //单个字符串判断回文的方法（双指针）
    public boolean checkMid(String a, int i, int j){
        while(i < j){
            if(a.charAt(i) != a.charAt(j)){
                break;
            }
            i++;
            j--;
        }
        return i >= j;
    }
}