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.

我用的是中心擴展法
因為回文字符串是以中心軸對稱的，所以如果我們從下標 i 出發(fā)，用2個指針向 i 的兩邊擴展判斷是否相等，那么只需要對0到
n-1的下標都做此操作，就可以求出最長的回文子串。但需要注意的是，回文字符串有奇偶對稱之分，即”abcba”與”abba”2種類型，
因此需要在代碼編寫時都做判斷。
設函數(shù)int Palindromic ( string &s, int i ,int j) 是求由下標 i 和 j 向兩邊擴展的回文串的長度，那么對0至n-1的下標，調用2次此函數(shù)：
int lenOdd = Palindromic( str, i, i ) 和 int lenEven = Palindromic (str , i , j )，即可求得以i 下標為奇回文和偶回文的子串長度。
接下來以lenOdd和lenEven中的最大值與當前最大值max比較即可。
這個方法有一個好處是時間復雜度為O(n2)，且不需要使用額外的空間。

public class Solution {public String longestPalindrome(String s) {int start = 0, end = 0;for (int i = 0; i < s.length(); i++) {int len1 = expandAroundCenter(s, i, i);int len2 = expandAroundCenter(s, i, i + 1);int len = Math.max(len1, len2);if (len > end - start) {start = i - (len - 1) / 2;end = i + len / 2;}}return s.substring(start, end + 1); }private int expandAroundCenter(String s, int left, int right) {int L = left, R = right;while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {L--;R++;}return R - L - 1; } }

還有一些動態(tài)規(guī)劃啊啥的其他的幾個方法，我也沒去弄懂，有興趣可以進這討論區(qū)看看。
LeetCode官方討論區(qū)

總結

以上是生活随笔為你收集整理的[LeetCode]--5. Longest Palindromic Substring的全部內容，希望文章能夠幫你解決所遇到的問題。

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