5. Longest Palindromic Substring

题意

返回字符串最长的回文子字符串

题解 １、暴击直接暴力遍历，当然结果不通过，时间Time Limit Exceeded

s.substr (pos, n) ，pos表示要截取的字符串的开始的位置，n 代表要截取的字符串的长度

class Solution {
public:
    bool isPalindrome(string s){
        int i=0, j=s.size()-1;
      while(i max){
                        max = temp.size();
                        res = temp;
                    }
                }
            }
        }
        return res;
    }
};

２、中心扩展方法

以babad为例，只需要从某一个中心开始，向左向右对比

以b为轴，向左右扩展，只扩展到b自身

以b|a之间为轴，向左右扩展，可以扩展出ba

依次寻找中心点，正常情况下对于每一个中心点，依次向二边扩展，然后查看回文长度，和起始位置，最后截取这段字符串即可。但是会有一种情况，就是ｍｉｄ位置附近是相同的字符如　ｂｂｂ　如下图所示。

这种情况　ｍｉｄＥｎｄ　需要向后移动二位，到红色箭头出。

class Solution {
public:
    string longestPalindrome(string s) {
        
        // edge cases
        if(s.length() == 0 || s.length() == 1) return s;
        
        // to hold max len and its starting index
        int maxLenBeginIndex = 0;
        int maxLen = 1;
        
        int mid = 0;
        while(mid < s.length()){
            
            // calculating middle window
            
            int midBegin = mid;
            int midEnd = mid;
            
            // handling even length palindromes; the middlemost chars will trivially match in even length case
            // so expand the middle window as long as possible
            while( midEnd + 1 < s.length() && s[midEnd] == s[midEnd + 1]){ midEnd++ ; }
            
            // for next iteration
            mid = midEnd + 1;
            
            // starting comparison in left and right windows
            
            // in case of odd len palindrome; both start from mid;
            // in case of even; midBegin and midEnd handles it all
            int leftWindow = midBegin;
            int rightWindow = midEnd;
            
            // expand the windows left and right simultaneously
            while(leftWindow - 1 >= 0 && rightWindow + 1 < s.length() && s[leftWindow - 1] == s[rightWindow + 1]){
                    leftWindow--;
                    rightWindow++;
            }
            
            // update maxLen is currLen > maxLen
            int currLen = rightWindow - leftWindow + 1;
            if( currLen  > maxLen ){
                maxLenBeginIndex = leftWindow;
                maxLen = currLen;
            }
        }
        
        return s.substr(maxLenBeginIndex, maxLen);
    }
};