Level：

??Medium

題目描述：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad" Output: "bab" Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd" Output: "bb"

思路分析：

??找出字符串的最長回文子串，我們遍歷字符串，把每一個(gè)字符當(dāng)做是回文串的中間元素，然后設(shè)置兩個(gè)指針向兩邊擴(kuò)展，如果兩個(gè)指針對(duì)應(yīng)的值相同則滿足回文串的要求，繼續(xù)向下擴(kuò)展，否則停止。以下一個(gè)元素為回文串的中間元素，進(jìn)行與上面相同的操作。最后我們選它們中間最長的串做為結(jié)果。

代碼：

public class Solution{int lo,maxlen; //回文串的起始坐標(biāo)，和回文串的長度public String longestPalindrome(String s){if(s.length()<2)return s;for(int i=0;i<s.length()-1;i++){extendPalidrome(i,i,s); //假設(shè)回文串的長度為奇數(shù)extendPalidrome(i,i+1,s);//假設(shè)回文串的長度為偶數(shù)}return s.substring(lo,lo+maxlen);}public void extendPalidrome(int start,int end,String s){while(start>=0&&end<s.length&&s.charAt(start)==s.charAt(end)){start--;end++;}if(maxlen<end-start-1){ //更新最長回文串的長度lo=start+1;maxlen=end-start-1;}} }

轉(zhuǎn)載于:https://www.cnblogs.com/yjxyy/p/10727989.html

總結(jié)

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

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