题解 | #最长回文子串#

C++ 防止遗忘 记录一下

• 中心扩充求最长回文子串

• 思路：
  选取字符串中的一个字符，向左和向右扩充，如果左右相等则记录长度，继续相等继续记录长度，不相等则返回最后的长度就是最长的；
  字符串长度可能是奇数，也可能是偶数，所以分两种情况扩充：取一个中心元素 & 取两个中心元素
  注意：记录长度时，len = j - i + 1不能犯在i--与j++后面，否则会出错，如i先减到-1了，j-i长度反而增加了
  （记住：相等就先记录长度，再去改变i j）

  class Solution {
  public:
    //扩充后，返回长度
    int extend(string& A,int i,int j,int n){
        int len = 0;
        while(i>=0&&j<n&&A[i]==A[j]){
            //相等则记录长度
            len = j-i+1;
            //记录长度后再去改变i j
            i--;
            j++;
  
        }
        return len;
    }
    int getLongestPalindrome(string A, int n) {
        // write code here
        if(A.size()<=1){
            return 1;
        }
        int max_len = 0;
        for(int i=0;i<n;i++){
            //有两种情况
            //一个中间元素
            int len1 = extend(A,i,i,n);
            //两个中间元素
            int len2 = extend(A,i,i+1,n);
            //先求出这两种情况的最大值
            int tmp = len1>len2?len1:len2;
            //再记录与先前记录最大值max_len二者中较大的
            max_len = max(max_len,tmp);
        }
        //返回最大的
        return max_len;
  
    }
  };