每日一题——分割两个字符串得到回文串

一开始的超时解答：

class Solution { public: bool checkPalindrome(string a) { int len = a.length(); int j = len - 1; for (int i = 0; i < j; i++) { if (a[i] != a[j]) { return false; } j--; } return true; } bool checkPalindromeFormation(string a, string b) { int len = a.length(); if (checkPalindrome(a) || checkPalindrome(b)) { return true; } string temp1 = ""; string temp2 = b; string temp3 = ""; string temp4 = a; for (int i = 0; i < len; i++) { temp1 += a[i]; temp2 = b; temp2 = temp2.erase(0, i+1); temp3 += b[i]; temp4 = a; temp4 = temp4.erase(0, i+1); if (checkPalindrome(temp1 + temp2) || checkPalindrome(temp3 + temp4)) { return true; } } return false; } };

然后发现超时之后进行更正判断，发现只需刨去字符串a与字符串b相同前后缀之后，判断剩余的字符串a/b是不是回文串即可。

class Solution {
public:
    bool checkPalindrome(string a) {
        int j = a.length() - 1;
        for (int i = 0; i < j; i++) {
            if (a[i] != a[j]) {
                return false;
            }
            j--;
        }
        return true;
    }

    string substr(string a, int i) {
        int len = a.length();
        a = a.erase(len - i, len);
        a = a.erase(0, i);
        return a;
    }

    bool checkPalindromeFormation(string a, string b) {
        int len = a.length();
        bool index1 = true;
        bool index2 = true;
        for (int i = 0; i < len; i++) {
            if (index1) {
                if (a[i] == b[len - 1 - i]) {
                    if (i >= len / 2) {
                        return true;
                    }
                }
                else {
                    if (checkPalindrome(substr(a, i)) || checkPalindrome(substr(b, i))) {
                        return true;
                    }
                    index1 = false;
                }
            }
            if (index2) {
                if (b[i] == a[len - 1 - i]) {
                    if (i >= len / 2) {
                        return true;
                    }
                }
                else {
                    if (checkPalindrome(substr(a, i)) || checkPalindrome(substr(b, i))) {
                        return true;
                    }
                    index2 = false;
                }
            }
        }
        return false;
    }
};

示例代码：

class Solution { public: bool f(string a,string b) { int l = 0, r = b.size() - 1; while (l <= r && a[l] == b[r]) ++l,--r; return ff(a,l,r) || ff(b,l,r); } bool ff(string a,int l,int r) { while (l <= r) { if (a[l] != a[r]) return false; ++l,--r; } return true; } bool checkPalindromeFormation(string a, string b) { return f(a,b) || f(b,a); } };