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

5.最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

回文子串是“aba” “abba”这种的 “abaca”不是

1. 这道题如果用暴力法，对每一个字符找他的回文子串时间复杂度会是O(n³)，在leetcode上一个很长的测试用例会超出时间限制。（由于没有通过，所以在本文最后再贴出暴力法的代码。）
   超时的测试用例：
   
2. 由于最近刚刚温习了动态规划，所以在优化算法的时候就想起了动态规划的方法，也就是如果i位置和j位置的字符相同且i+1到j-1的字符串是一个回文子串的话，那么从i到j的字符串也是一个回文子串。

class Solution {
   public:    string longestPalindrome(string s) {
           int maxlength=1,flag=0;        if(s.size()==0){
               return "";        }        vector
   
    
      > str(s.size(),vector
     
      (s.size()));//定义一个二维数组来表示回文子串的起点和终点       for (int i=0; i
     
    
   

通过时间：

class Solution {
   public:    string longestPalindrome(string s) {
           int maxlength=1,flag=0;        if(s.size()==0){
               return "";        }        for(int i=0;i
   
    i;j--){
                   int flagi=i;                int flagj=j;                while(s[flagj]==s[flagi]){
                       if(flagi==flagj || flagi==flagj-1){
                           if( (j-i+1) > maxlength ){
                           maxlength=j-i+1;                        flag=i;                        }                        break;                    }                    flagj--;                    flagi++;                }            }        }        return s.substr(flag,maxlength);    }};
   

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