本文共 2669 字，大约阅读时间需要 8 分钟。

题目描述如下：

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.

即求最长的回文子串。回文字符串即从左往右和从右往左的字符组成是一样的，如aba，但abc便不是。

1.最首先想到的肯定是暴力求解法，但是其时间复杂度是O(N³),最后TLE；

2.使用动态规划求解。首先求出状态转移方程：

  我们定义P[i,j] 表示从i到j组成的子串是否是回文字符串，若是，p[i,j] = true，否则，p[i,j] = false;

  p[i,j] = p[i + 1, j - 1] & s[i] == s[j]，很好理解，当从第I+1到j-1组成的子串是回文字符串且第i个字符与第j个字符相同时，从第i个字符到第j个字符组成的子   串肯定也是回文字符串；

  其中：p[i,i]  = true, p[i, i + 1] = s[i] == s[i + 1];

  由状态转移方程可知，该问题应自下往上自左往右求解；Java代码如下：

public class Solution {    public String longestPalindrome(String s) {        if(s == null)            return null;        if(s.length() == 0)            return "";        int sLen = s.length();        boolean[][] dp = new boolean[sLen][sLen];        int beginIndex = 0;        int maxLen = 1;        for(int i = 0; i < sLen; i++)            dp[i][i] = true;        for(int i = 0; i < sLen - 1; i++)            if(s.charAt(i) == s.charAt(i + 1)){                dp[i][i + 1] = true;                beginIndex = i;                maxLen = 2;            }        for(int len = 3; len < sLen + 1; len++){            for(int i = 0; i < sLen - len + 1; i++){                int j = i + len - 1;                if(dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)){                    dp[i][j] = true;                    beginIndex = i;                    maxLen = len;                }//end if            }//end for i        }//end for i        return s.substring(beginIndex, beginIndex + maxLen);    }}

3.自中心向外扩展法，很巧妙又很好理解的方法。回文字符串的典型特征便是关于中心特征，当然，当字符串长度为奇数和为偶数时要分开处理：当长   度为奇数时，回文字符串关于最中间的字符对称；当长度为偶数时，回文字符串关于中心轴对称；这样，对于长度为n的字符串，一个有2N-1个中心     位置（每个字符所在位置和每两个字符中间的位置），针对每个中心位置进行扩展，即可成功求解。

  该解法的时间复杂度同样是O（n2），但是空间复杂度为O（1），代码如下：

public class Solution {    public String longestPalindrome(String s) {        if(s == null)            return null;        if(s.length() == 0)            return "";        String longest = new String();                int sLen = s.length();        for(int i = 0; i < sLen; i++){            String odd = expandPalindrome(s, i, i);            if(longest.length() < odd.length())                longest = odd;            String even = expandPalindrome(s, i, i + 1);            if(longest.length() < even.length())                longest = even;        }//end for i         return longest;    }        public String expandPalindrome(String s, int l, int r){        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){            l--;            r++;        }        return s.substring(l + 1, r);    }}

转载地址：http://hlbvb.baihongyu.com/