# Leetcode 5. Longest Palindromic Substring
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/longest-palindromic-substring/ 。

想法 :

陣列代表的狀態為這一個字串是否為廻文。

狀態轉移為 : 去比較前一段更小的區段是否已經是廻文，如果是就加上它。

原本是寫順向的，後來發現要逆向，因為這樣才能知道更小的區段是否已經做過了。

時間複雜度 : O(n^2)。

程式碼 :

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