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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

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

方法一：双指针

思路

记字符串的长度为 n，分割的下标为 k，即下标 k 之前的字符构成前缀，下标 k 和之后的字符构成后缀，前缀长度为 k，后缀长度为 n-k，0 \leq k \leq n。

接下来需要判断 a_\textit{prefix} + b_\textit{suffix 或者 b_\textit{prefix} + a_\textit{suffix 能否构成回文字符串，首先判断 a_\textit{prefix} + b_\textit{suffix 能否构成回文字符串。这个字符串的起始位置是由 a 组成的，末尾位置是由 b 构成的。要想构成回文，起始的部分和末尾的部分必须是倒序相等的，这个可以用双指针来逐位判断。当遇到不相等的情况时，则说明遇到了分割点，分割的位置可能是左侧的指针，也可能是右侧的指针。如果分割点是左侧的指针，则需要 b 在双指针之间的字符串构成回文；如果分割点是右侧的指针，则需要 a 在双指针之间的字符串构成回文。这二者满足其一即可。

判断 b_\textit{prefix} + a_\textit{suffix 能否构成回文字符串也是类似的思路。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        return self.checkConcatenation(a, b) or self.checkConcatenation(b, a)
    
    def checkConcatenation(self, a: str, b: str) -> bool:
        n = len(a)
        left, right = 0, n-1
        while left < right and a[left] == b[right]:
            left += 1
            right -= 1
        if left >= right:
            return True
        return self.checkSelfPalindrome(a, left, right) or self.checkSelfPalindrome(b, left, right)

    def checkSelfPalindrome(self, a: str, left: int, right: int) -> bool:
        while left < right and a[left] == a[right]:
            left += 1
            right -= 1
        return left >= right
[sol1-Java]
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
class Solution {
    public boolean checkPalindromeFormation(String a, String b) {
        return checkConcatenation(a, b) || checkConcatenation(b, a);
    }

    public boolean checkConcatenation(String a, String b) {
        int n = a.length();
        int left = 0, right = n - 1;
        while (left < right && a.charAt(left) == b.charAt(right)) {
            left++;
            right--;
        }
        if (left >= right) {
            return true;
        }
        return checkSelfPalindrome(a, left, right) || checkSelfPalindrome(b, left, right);
    }

    public boolean checkSelfPalindrome(String a, int left, int right) {
        while (left < right && a.charAt(left) == a.charAt(right)) {
            left++;
            right--;
        }
        return left >= right;
    }
}
[sol1-C#]
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
public class Solution {
    public bool CheckPalindromeFormation(string a, string b) {
        return checkConcatenation(a, b) || checkConcatenation(b, a);
    }

    public bool checkConcatenation(string a, string b) {
        int n = a.Length;
        int left = 0, right = n - 1;
        while (left < right && a[left] == b[right]) {
            left++;
            right--;
        }
        if (left >= right) {
            return true;
        }
        return CheckSelfPalindrome(a, left, right) || CheckSelfPalindrome(b, left, right);
    }

    public bool CheckSelfPalindrome(string a, int left, int right) {
        while (left < right && a[left] == a[right]) {
            left++;
            right--;
        }
        return left >= right;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func checkPalindromeFormation(a, b string) bool {
    return checkConcatenation(a, b) || checkConcatenation(b, a)
}

func checkConcatenation(a, b string) bool {
    left, right := 0, len(a)-1
    for left < right && a[left] == b[right] {
        left++
        right--
    }
    if left >= right {
        return true
    }
    return checkSelfPalindrome(a[left:right+1]) || checkSelfPalindrome(b[left:right+1])
}

func checkSelfPalindrome(s string) bool {
    left, right := 0, len(s)-1
    for left < right && s[left] == s[right] {
        left++
        right--
    }
    return left >= right
}
[sol1-C++]
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
class Solution {
public:
    bool checkSelfPalindrome(const string &a, int left, int right) {
        while (left < right && a[left] == a[right]) {
            left++;
            right--;
        }
        return left >= right;
    }

    bool checkConcatenation(const string &a, const string &b) {
        int n = a.size();
        int left = 0, right = n - 1;
        while (left < right && a[left] == b[right]) {
            left++;
            right--;
        }
        if (left >= right) {
            return true;
        }
        return checkSelfPalindrome(a, left, right) || checkSelfPalindrome(b, left, right);
    }

    bool checkPalindromeFormation(string a, string b) {
        return checkConcatenation(a, b) || checkConcatenation(b, a);
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool checkSelfPalindrome(const char *a, int left, int right) {
    while (left < right && a[left] == a[right]) {
        left++;
        right--;
    }
    return left >= right;
}

bool checkConcatenation(const char *a, const char *b) {
    int n = strlen(a);
    int left = 0, right = n - 1;
    while (left < right && a[left] == b[right]) {
        left++;
        right--;
    }
    if (left >= right) {
        return true;
    }
    return checkSelfPalindrome(a, left, right) || checkSelfPalindrome(b, left, right);
}

bool checkPalindromeFormation(char * a, char * b){
    return checkConcatenation(a, b) || checkConcatenation(b, a);
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var checkPalindromeFormation = function(a, b) {
    return checkConcatenation(a, b) || checkConcatenation(b, a);
}

const checkConcatenation = (a, b) => {
    const n = a.length;
    let left = 0, right = n - 1;
    while (left < right && a[left] === b[right]) {
        left++;
        right--;
    }
    if (left >= right) {
        return true;
    }
    return checkSelfPalindrome(a, left, right) || checkSelfPalindrome(b, left, right);
}

const checkSelfPalindrome = (a, left, right) => {
    while (left < right && a[left] === a[right]) {
        left++;
        right--;
    }
    return left >= right;
};

复杂度分析

  • 时间复杂度：O(n)，其实 n 是输入字符串的长度。每个字符串最多遍历两遍。

  • 空间复杂度：O(1)，仅使用常数空间。

 Comments
On this page
1616-分割两个字符串得到回文串