[leetcode] 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, and there exists one unique longest palindromic substring.

思路：建一个method来找某一个特定位置为中心的最长可能palindrome, 返回此长度。（注意有两种情况，长度为偶数和为奇数）。然后从s中心向两边开始依次找对应各个位置的最长长度，结果记录在数组num[i] 里，同时track 当前最长值，如果满足 2*middle - i < max/2 这个条件就没有必要继续了。


public class Solution {
    public String longestPalindrome(String s) {
         if (s == null)
        return null;
        if(s == "" || s.length()==1)
        return s;
//create an array to store length of longest palindrome that centers at each position.
        int[] num = new int[s.length()];
         for(int i = 0; i<num.length; i++)
        num[i] = 1;
 
        int middle = s.length()/2;
   
//call method to calculate value of num[i], start with middle position;              
        num[middle] = findLongestPalindromethatCenterHere(s, middle);
        num[0] = findLongestPalindromethatCenterHere(s, 0);
        int index_max, max;
        if(num[0]<num[middle])
        {
        index_max = middle;
            max = num[middle];
        }
        else
        {
        index_max = 0;
            max = num[0];
        }
        for(int i = middle+1; i<middle*2; i++)
        {
        num[i] = findLongestPalindromethatCenterHere(s, i);
        if(num[i]>max)
        {
        max = num[i];
        index_max = i;
        }        
        num[middle*2-i] = findLongestPalindromethatCenterHere(s, middle*2-i);
        if(num[middle*2-i]>max)
        {
        max = num[middle*2-i];
        index_max = middle*2-i;
        }      
        if(2*middle - i < max/2)  //max already found here, no need to continue.
        break;
        }
        if(num[index_max]%2 == 0)
        return s.substring(index_max-num[index_max]/2+1, index_max+num[index_max]/2+1);
        else
        return s.substring(index_max-num[index_max]/2, index_max+num[index_max]/2+1);
    }

//this method is to find length of possible longest palindrome that centers at specific position.
//be aware that there are two possibilities to address.
public int findLongestPalindromethatCenterHere(String s, int center)
{
//assume length of palindrome is a odd number.
 int max1 = 1;
 int start = center-1;
 int end = center+1;

 while(start>=0 && end<s.length())
 {
 if(s.charAt(start) == s.charAt(end))
 max1 = max1+2;
 else
 break;
 start--;
 end++;
 }
//assume length is an even number.
 int max2 = 0;
 start = center;
 end = center+1;
 while(start>=0 && end<s.length())
 {
 if(s.charAt(start) == s.charAt(end))
 max2 = max2+2;
 else
 break;
 start--;
 end++;
 }
 return Math.max(max1, max2);
}
}