題目：https://leetcode-cn.com/problems/longest-palindromic-substring/
給你一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。

我的方法一：動(dòng)態(tài)規(guī)劃

一看到最長(zhǎng)、最優(yōu)、最少等字眼，一般就是動(dòng)態(tài)規(guī)劃來(lái)解決。

步驟

1. 確認(rèn)子問(wèn)題
   1.1 最后一步：最大回文或者包括最后一個(gè)字符，或者不包括最后一個(gè)字符；
   1.2 子問(wèn)題： 加上最后一個(gè)字符后，或者最長(zhǎng)回文還是沒加最后一個(gè)字符對(duì)應(yīng)的最長(zhǎng)回文，或者是以最后一個(gè)字符為結(jié)尾的更長(zhǎng)的回文
2. 轉(zhuǎn)移方程
   dp[n] = max(dp[n-1], 以最后一個(gè)字符為結(jié)尾的最大回文)
3. 邊界條件和初始條件
   3.1 當(dāng)字符串為空時(shí)，直接返回空
   3.2 dp[n]代表的意義指以第n位字符為結(jié)尾的字符串的最大回文，所以n從0開始，最大是s.size()-1
   3.3 求以最后一個(gè)字符為結(jié)尾的最大回文時(shí)，如果已經(jīng)發(fā)現(xiàn)長(zhǎng)度已經(jīng)小于了dp[n-1]的長(zhǎng)度，那么直接停止即可；
   3.4 初始條件，dp[0] = s[0]
4. 計(jì)算順序
   dp[0] dp[1] dp[n]

復(fù)雜度

時(shí)間復(fù)雜度：O(nlogn)，因?yàn)樾枰?jì)算n次是O(n)，另外每次查找以最后一個(gè)字符為結(jié)尾的回文復(fù)雜度是O(n)，由于需要計(jì)算的長(zhǎng)度從0依次變?yōu)閚，所以實(shí)際復(fù)雜度是O(logn)，所以總體時(shí)間復(fù)雜度是O(nlogn) = O(n)*O(logn)
空間復(fù)雜度：O(n)，因?yàn)閐p數(shù)組的長(zhǎng)度是n

代碼

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() == 0){
            return "";
        }

        vector<string> dp(s.size());
        const char* str = s.c_str();
        int size = s.size();
        dp[0] = string(str, str+1);

        //dp[n] = max(dp[n-1], ***);

        int left = 0;
        for(int i = 1; i<size; i++){
            left = 0;
            while(left<i){
                if(isMirror(str, left, i)){
                    break;
                }

                left++;
            }
            
            if(i-left+1 > dp[i-1].size()){
                dp[i] = string(str+left, str+i+1);
            }else{
                dp[i] = dp[i-1];
            }
        }

        return dp[size-1];
    }

private:
    bool isMirror(const char* str, int left, int right){
        while(left<right){
            if(str[left] != str[right]){
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
};

優(yōu)化

由于dp[n]只和前一個(gè)有關(guān)，所以沒有必要保留更前面的結(jié)果，所以用一個(gè)字符串保存當(dāng)前的最大回文字符串即可，這樣空間復(fù)雜度從O(n)降為了O(1)，實(shí)際結(jié)果從30M降到了24M。

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() == 0){
            return "";
        }

        const char* str = s.c_str();
        int size = s.size();

        string max_loop_str = string(str, str+1);
        //dp[n] = max(dp[n-1], ***);

        int left = 0;
        for(int i = 1; i<size; i++){
            left = 0;
            while(left<i){
                if(isMirror(str, left, i)){
                    break;
                }

                left++;
            }
            
            if(i-left+1 > max_loop_str.size()){
                max_loop_str = string(str+left, str+i+1);
            }
        }

        return max_loop_str;
    }

private:
    bool isMirror(const char* str, int left, int right){
        while(left<right){
            if(str[left] != str[right]){
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
};

其他優(yōu)化方法

時(shí)間O(n)的算法：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/