Longest Palindromic Substring(最长回文子串)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

从字符串中找出最长的回文子串，该长度的子串可能有多个，这里只要找到一个就够了。。前面有判断回文回文的题目。

这里找出最长回文子串，可以直接双层for循环，对于每个子字符串都判断是否是回文，判断回文也要遍历，所以此时时间复杂度是O(N^3)。很大。

这里找出回文串，根据回文串的特点，我们可以从一个字符（或两个）向两边扩展，判断两边对应字符是否相等，如果相等，这两个相等字符就可以加入回文串，然后继续往两边找。

class Solution {
    int start;//回文串的起始位置
    int maxLen;//最大长度，知道这两个参数也就知道了子串
    /**
        直接暴力解法时间复杂度为O(n^3)。
        对于回文：从中间字符往两边移动，两边的字符都是对应相同的，（奇数长度就是从中间开始往两边，偶数长度就是从中间两个开始都相等）。
        这里遍历每个字符，从该字符往两边移动，比较对应字符是否相等。所以用两个变量往两边移动，当两个变量指向的值不相等时，回文结束。
        由于奇数长度时，中间有孤立的一个，所以此时两个指针同时指向自己。因为遍历的时候不知道该字符所属的回文的长度，所以同时判断两种情况。
    */
    public String longestPalindrome(String s) {
        if(s==null||s.length()==0) return null;
        if(s.length()==1) return s;
        for(int i=0;i<s.length()-1;i++){  //最后一个不可能是中间奇数的字符
            //考虑两种情况。1.奇数长度，从当前字符向两边扩展。2，偶数长度，从当前字符和后一个字符向两边扩展（这两个字符也得相等）
            extendPalindrome(s,i,i);
            extendPalindrome(s,i,i+1);
        }
    return s.substring(start,start+maxLen);
 }
    /*
        从j、k两个位置开始往两边扩展找出回文。
    */
    public void extendPalindrome(String str,int j,int k){
        while(j>=0&&k<=str.length()-1&&str.charAt(j)==str.charAt(k)){
            j--;
            k++;
        }
        
        if(maxLen<k-j-1){
            start=j+1;
            maxLen=k-j-1;
        }
    }
}