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

链接：1616.分割两个字符串得到回文串
难度：Medium
标签：双指针、字符串
简介：请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。

题解 1 - python

• 编辑时间：2023-03-18
• 执行用时：108ms
• 内存消耗：15.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def check(s: str):
            l, r = 0, len(s)-1
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True
        n, cnt = len(a), 0
        while cnt < n and a[cnt] == b[n-1-cnt]:
            cnt += 1
        if cnt >= n//2 or check(a[cnt:n-cnt]) or check(b[cnt:n-cnt]):
            return True
        cnt = 0
        while cnt < n and b[cnt] == a[n-1-cnt]:
            cnt += 1
        if cnt >= n//2 or check(a[cnt:n-cnt]) or check(b[cnt:n-cnt]):
            return True
        return False

题解 2 - rust

• 编辑时间：2023-03-18
• 执行用时：12ms
• 内存消耗：3.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn check_palindrome_formation(a: String, b: String) -> bool {
        let check = |s: &[char]| {
            let (mut l, mut r) = (0, s.len() - 1);
            while l < r {
                if s[l] != s[r] {
                    return false;
                }
                l += 1;
                r -= 1;
            }
            true
        };
        let a = a.chars().collect::<Vec<char>>();
        let b = b.chars().collect::<Vec<char>>();
        let (n, mut cnt) = (a.len(), 0);
        while cnt < n && a[cnt] == b[n - 1 - cnt] {
            cnt += 1;
        }
        if cnt >= n / 2 || check(&a[cnt..n - cnt]) || check(&b[cnt..n - cnt]) {
            return true;
        }
        cnt = 0;
        while cnt < n && b[cnt] == a[n - 1 - cnt] {
            cnt += 1;
        }
        if cnt >= n / 2 || check(&a[cnt..n - cnt]) || check(&b[cnt..n - cnt]) {
            return true;
        }
        false
    }
}

题解 3 - cpp

• 编辑时间：2023-03-18
• 执行用时：52ms
• 内存消耗：28.5MB
• 编程语言：cpp
• 解法介绍：贪心a前缀和b后缀最大匹配个数，a后缀和b前缀最大匹配个数。

class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        int n = a.size(), cnt = 0;
        while (cnt < n && a[cnt] == b[n - 1 - cnt]) cnt++;
        if (cnt >= n / 2 || check(a.substr(cnt, n - cnt * 2)) || check(b.substr(cnt, n - cnt * 2))) return true;
        cnt = 0;
        while (cnt < n && b[cnt] == a[n - 1 - cnt]) cnt++;
        if (cnt >= n / 2 || check(a.substr(cnt, n - cnt * 2)) || check(b.substr(cnt, n - cnt * 2))) return true;
        return false;
    }
    bool check(string s) {
        for (int l = 0, r = s.size() - 1; l < r; l++, r--)
            if (s[l] != s[r]) return false;
        return true;
    }
};