题解 | #最长回文子串#

比较经典的回文判断题型。由于题目要求时间复杂度为O(n^2)，故考虑较为直接的暴力解法。
使用一个二重循环，第一重循环i从数组的第一个元素开始，第二重循环j从数组的最后一个元素开始，每趟循环都判断从i到j是否构成回文，若构成，则直接退出内层循环，在外层更新最大值。当i到j的字符串长度小于最大值时，直接退出内层循环，不更新最大值。
这样做的好处是，当一个很长的字符串本身就是一个回文时，时间复杂度无限接近O(n)。而最坏的情况，一个很长的字符串中不存在回文时，时间复杂度则介于O(n^2)与O(n^3)之间。平均时间复杂度介于O(nlogn)与O(n^2)之间，满足题目要求。而不借助辅助数组，故空间复杂度为O(1)。
这里判断给定的字符串是否是回文的逻辑也稍微提一下。从字符串两端开始向中间比较，一旦发现有不一样的两个字符，则不是回文。

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int max = 1;
        for(int i = 0;i < A.length();i++){
            int len = 1;
            int j = 0;
            bool beenCut = false;
            for(j = n - 1;j>i;j--){
                //cut
                if(j-i+1 < max){
                    beenCut = true;
                    break;
                }
                if(judge(A.substr(i,j-i+1))){
                    break;
                }
            }
            if(beenCut){
                len = 1;
            }
            else{
                len = j - i + 1;
            }
            if(len > max){
                max = len;
            }
        }
        return max;
    }
    bool judge(string s){
        for(int i = 0;i < s.length()/2;i++){
            if(s[i] != s[s.length() - 1 - i]){
                return false;
            }
        }
        return true;
    }
};