5.md

5. 最长回文子串

DP

dp[i][j]表示从i到j的子串是否回文。

时间复杂度：O(n²)。

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size();
        bool dp[size][size];
        memset(dp, false, sizeof(dp));
        int start = 0, len = 0;
        for (int i = size-1; i >= 0; i--) {
            for (int j = i; j < size; j++) {
                if (j == i) {
                    dp[i][j] = true;
                } else {
                    if (s[i] == s[j]) {
                        if (j == i+1) {
                            dp[i][j] = true;
                        } else {
                            dp[i][j] = dp[i+1][j-1];
                        }
                    } else {
                        dp[i][j] = false;
                    }
                }
                if (dp[i][j] && j-i+1 > len) {
                    len = j-i+1;
                    start = i;
                }
            }
        }
        return s.substr(start, len);
    }
};