# 5 - Longest Palindromic Substring

解法一 - DP

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        // Init one-letter and two-letter cases
        for(int i=0; i<n; i++) 
            for(int j=0; j<n; j++) 
                if(j-i < 2) dp[i][j] = (s[i] == s[j]);

        // Recurrence
        for(int i=n-3; i>=0; i--) {
            for(int j=i+2; j<n; j++) {
                dp[i][j] = dp[i+1][j-1] && (s[i] == s[j]);
            }
        } 

        // Get the answer
        string res = s.substr(0,1);
        int maxL = 1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(dp[i][j] && (j-i+1)>maxL) {
                    maxL = j-i;
                    res = s.substr(i, j-i+1);
                }
            }
        }

        return res;
    }
};

可以稍微修改一下程式碼，合併 Init 跟 Recurrence 的地方：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        // Recurrence
        for(int i=n-3; i>=0; i--) {
            for(int j=i+2; j<n; j++) {
                dp[i][j] = (j-i<2 || dp[i+1][j-1]) && (s[i] == s[j]);
            }
        } 

        // Get the answer
        string res = s.substr(0,1);
        int maxL = 1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(dp[i][j] && (j-i+1)>maxL) {
                    maxL = j-i;
                    res = s.substr(i, j-i+1);
                }
            }
        }

        return res;
    }
};