給定一個字符串 s，找到 s 中最長的回文子串。你可以假設?s 的最大長度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
示例 2：

輸入: "cbbd"
輸出: "bb"

?

思路：中心擴展法

每次都以一個點或者兩個點為中心，向兩邊擴散，如果左右字符相等就繼續(xù)遍歷

以一個點為中心是因為回文字符串長度可能是奇數(shù)，比如：ababa

以兩個點為中心是因為回文字符串長度可能是偶數(shù)，比如：ababab

代碼：

class?Solution?{

????public?String?longestPalindrome(String?s)?{

????????if(s.length()==0){

????????????return?s;

????????}

????????int?start=0,end=0;

????????for(int?i=0;i<s.length();i++){

????????????int?ji?=?helper(s,i,i);

????????????int?ou?=?helper(s,i,i+1);

????????????int?temp?=?Math.max(ji,ou);//比較以一個點為中心和以兩個點為中心的長度

????????????if(temp>end-start){

????????????????start?=?i-(temp-1)/2;

????????????????end?=?i+temp/2;

????????????}

????????}

????????return?s.substring(start,end+1);

????}

????public?int?helper(String?s,int?i,int?j){

????????while(i>=0&&j<s.length()){

????????????if(s.charAt(i)==s.charAt(j)){

????????????????i--;

????????????????j++;

????????????}else{

????????????????break;

????????????}

????????}

????????return?j-i-1;

????}

}

總結(jié)

以上是生活随笔為你收集整理的Leetcode--5. 最长回文子串(java)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。