LeetCode[5] 最长的回文子串

题目描述

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.

即给定一个字符串,返回该字符串最长的回文子串
如给出“acabcddcbadike”,返回“abcddcba”。

思路

回文子串分为长度为偶数(中间两个字符相同,就像示例)和长度为奇数两种。
从头往后遍历s.length()趟,第i趟指针j,k从i(奇数)或j从i,k从i+1(偶数)向两边扩散(s.charAt(i)和s.charAt(j)相等才扩散),k-j-1为该回文子串长度,若比之前maxlen大,则更新maxlen。

代码如下

public class Solution {
private int lo,maxlen;//子串的起始和长度
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); //子串长度为奇数
extendPalindrome(s,i,i+1);//子串长度为偶数
}
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;
}
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :