5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

找最长的回文子串。longest + palindromic => DP。遍历所有可能的回文找最长的。dp[i][j]表明[i, j]是否为回文。

/*
 * @lc app=leetcode id=5 lang=cpp
 *
 * [5] Longest Palindromic Substring
 */
class Solution {
public:
    string longestPalindrome(string s) {
        const int N = s.size();
        if (N == 0) return s;
        int r = 1;
        vector<vector<bool>> dp(N, vector<bool>(N));
        for (int i = 0; i < N; ++i) dp[i][i] = true;
        string res(1, s[0]);
        for (int i = N - 2; i >= 0; --i) {
            for (int j = i + 1; j < N; ++j) {
                if (s[i] == s[j] && (j == i + 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    const auto len = j - i + 1;
                    if (len > r) {
                        r = len;
                        res = s.substr(i, len);
                    }
                }
            }
        }
        return res;
    }
};