題目來源
求字符串里最長的回文串碍讨。最簡單的方法就是暴力直接搜拆火。
代碼如下：

class Solution {
public:
   string longestPalindrome(string s) {
       int n = s.size(), longest = 0;
       string res = "";
       if (n == 0)
           return res;
       for (int i=0; i<n; i++)
           for (int j=i; j<n; j++)
               if (isPalindrome(s, i, j) && isPalindrome(s, i, j) > longest) {
                   longest = isPalindrome(s, i, j);
                   res = s.substr(i, j-i+1);
               }
       return res;
   }
   
   int isPalindrome(string s, int start, int end)
   {
       int i = start, j = end;
       while (i <= j) {
           if (s[i] != s[j])
               return 0;
           i++, j--;
       }
       return end - start + 1;
   }
};

代碼想法都很簡單，但是復(fù)雜度高達(dá)O(n^3)脸狸， 這種弱雞解法的結(jié)局只有一個…那就是超時钳枕。好吧缴渊，再想想。然后想了個O(n^2)的弱雞解法鱼炒，就是把i , j的結(jié)果存一下衔沼，實(shí)際上就是DP。然后解法如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string res = "";
        if (n == 0)
            return res;
        res = s[0];
        int longest = 1;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i=0; i<n; i++)
            dp[i][i] = 1;
        for (int i=1; i<n; i++)
            for (int j=0; j<n; j++)
                if (j+i<n && ((j+i-1 >= j+1 && dp[j+1][j+i-1] == 1) || i == 1) && s[j] == s[j+i]) {
                    dp[j][j+i] = 1;
                    if (i+1 > longest) {
                        longest = i + 1;
                        res = s.substr(j, i+1);
                    } 
                }
        return res;
    }
};

可以AC昔瞧，不過解法真的很爛指蚁，應(yīng)該是有O(n)的方法的吧。
看了下自晰，并沒有欣舵，不過優(yōu)化了很多，做法是從頭到尾遍歷缀磕，然后從中間向兩邊擴(kuò)展。這樣確實(shí)快很多劣光。差不多接近O(n)了吧袜蚕。

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n == 0)
            return "";
        int start = 0, maxLen = 1;
        for (int i=0; i<n; ) {
            int j = i, k = i;
            while (k < n - 1 && s[k+1] == s[k])
                k++;
            i = k + 1;
            while (k < n - 1 && j > 0 && s[k+1] == s[j-1]) {
                j--, k++;
            }
            if (maxLen < k - j + 1) {
                start = j;
                maxLen = k - j + 1;
            }
        } 
        return s.substr(start, maxLen);
    }
};