題目描述
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.
即給定一個(gè)字符串洞豁，返回該字符串最長(zhǎng)的回文子串
如給出“acabcddcbadike",返回“abcddcba"。
思路
回文子串分為長(zhǎng)度為偶數(shù)（中間兩個(gè)字符相同荒给，就像示例）和長(zhǎng)度為奇數(shù)兩種丈挟。
從頭往后遍歷s.length()趟，第i趟指針j志电，k從i（奇數(shù)）或j從i曙咽，k從i+1（偶數(shù)）向兩邊擴(kuò)散（s.charAt(i)和s.charAt(j)相等才擴(kuò)散），k-j-1為該回文子串長(zhǎng)度挑辆，若比之前maxlen大例朱，則更新maxlen。
代碼如下
public class Solution {
private int lo,maxlen;//子串的起始和長(zhǎng)度
public String longestPalindrome(String s) {
int len=s.length();
if (len<2)
return s;
for (int i=0;i<len-1;i++){//n躺遍歷
extendPalindrome(s,i,i); //子串長(zhǎng)度為奇數(shù)
extendPalindrome(s,i,i+1);//子串長(zhǎng)度為偶數(shù)
}
return s.substring(lo,lo + maxlen);
}
private void extendPalindrome(String s,int j,int k){
while(j>=0 && k<s.length() && s.charAt(j)==s.charAt(k)){
--j;
++k;
}
if(maxlen<k-j-1){
lo=j+1;
maxlen=k-j-1;
}
}
}
