Leetcode 5. Longest Palindromic Substring

difficulty ： secondary
frequency ：117
subject ： Give you a string s, find s The longest palindrome substring in .

How to solve the problem ： Center expansion method

• 1. If string It's odd , So it is a single center expansion .
• 2. If it's an even number , So it's a two center expansion .
• 3. The return value is the length of palindrome substring
• 4. According to length and Center , Find substring

class Solution {
    
  public String longestPalindrome(String s) {
    
      int len=s.length();
      if(len<=1) return s;

      int [] res=new int[2];
      int maxlen=0;
      //for Loop cannot be i and i+1 Transboundary .
      for(int i=0;i<len-1;i++){
    
          int [] odd=centerspread(s,i,i);
          int [] even=centerspread(s,i,i+1);
          int [] max=odd[1]>even[1]?odd:even;
          if(max[1]>maxlen){
    
              res=max;
              maxlen=max[1];
          }
      }
      return s.substring(res[0],res[0]+res[1]);
      
  }

	// The return value of the function is   An array { first place : Start subscript , Second : length }
    public int[] centerspread(String s,int left,int right){
    
        int len=s.length();
        while(left>=0&&right<=len-1){
    
        	// The methods here need to be remembered 
            if(s.charAt(left)==s.charAt(right)){
    
                right++;
                left--;
            }
            else{
    
                break;    
            }
        }
        return new int[]{
    left+1,(right-1)-(left+1)+1}; //  there left and right One more 
    }
}
 

Be careful ：

1. Write one more function to calculate the maximum number of palindromes after fixing the center each time

• Remember here s.charAt（ Subscript ）
• The return value of the function is An array { first place : Start subscript , Second : length }
• final right and left It's an extra step

2. Because I don't know whether the maximum palindrome is an odd length or an even length , So it all counts , Then take the longest . From the center 0 To i-2 It's all traversal .

• for In circulation i and i+1 Don't cross the border