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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你两个字符串 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⁵
a.length == b.length
a 和 b 都只包含小写英文字母

# 思路

先找出最长能匹配的前缀和后缀，判断即可

# 解法


class Solution {
    public boolean checkPalindromeFormation(String a, String b) {
        // 只需判断四种情况：a, b, aP+bS, bP+aS
        // 判断a, b
        if (isPanlindrom(a) || isPanlindrom(b)) {
            return true;
        }
        // 判断aP+bS, bP+aS，注意直接从最长位找起匹配即可
        if (isOk(a, b) || isOk(b, a)) {
            return true;
        }
        return false;
    }

    private boolean isOk(String a, String b) {
        // 先匹配出最长aPrefix和bSuffix
        int len = a.length();
        int idx = 0;
        while (a.charAt(idx) == b.charAt(len - idx - 1)) {
            idx++;
            if (idx >= b.length() - idx) {
                return true;
            }
        }
        // 判断剩下的a[idx:len-idx] 或 b[idx:len-idx], 如果是回文串加上对应的aPrefix和bSuffix则可得到完整结果
        return isPanlindrom(a.substring(idx, len - idx)) || isPanlindrom(b.substring(idx, len - idx));
    }

    private boolean isPanlindrom(String str) {
        int l = 0;
        int r = str.length() - 1;
        while (l <= r) {
            if (str.charAt(l) != str.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

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
34
35
36
37
38
39
40
41
42

# 总结

分析出几种情况，然后分别对各个情况实现

#Java