[M枚举] lc5. 最长回文子串(枚举+中心拓展+区间dp)「建议收藏」

// 暴力直接算，即中心扩散，时间复杂度为O(n^2) 字符串最好能在1000以内的长度
// 动规可以算，时间复杂度为O(n^2) 
// 马拉车算法，专门解决最长回文子串问题，时间复杂度能达到O(n)

class Solution { 
   
public:
    string longestPalindrome(string s) { 
   
        int n = s.size();
        string res;
        for (int i = 0; i < n; i ++ ) { 
   
            // 处理回文串长度为奇数的情况
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) l -- , r ++ ;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);   // 左闭右开区间

            // 处理回文串为偶数的情况
            l = i, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) l -- , r ++ ;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
        }
        return res;
    }
};

class Solution { 
   
public:
    string longestPalindrome(string s) { 
   
        int n = s.size();
        if (n < 2) return s;

        // f[i][j] 表示 s[i:j] 这一段是回文串，区间 dp
        vector<vector<bool>> f(n, vector<bool>(n));

        // 长度为 1 的串必然是回文的
        for (int i = 0; i < n; i ++ ) f[i][i] = true;

        // 最短的回文串长度就是 1，在这初始化 mx=0 的话会出错
        // 可能整个串中都没有长度大于 2 的回文串，那么最后 substr() 的时候就会出错了，如 "ac"
        int mx = 1, l = 0;      
        for (int len = 2; len <= n; len ++ ) { 
         // 枚举子串长度
            for (int i = 0; i < n; i ++ ) { 
            // 枚举左边界。根据长度得到右边界下标
                int j = len + i - 1;                // [i, j] 有 j-i+1 个数
                if (j >= n) break;                  // 右边界越界，左区间不需要再向右了，退出当前循环

                if (s[i] != s[j]) f[i][j] = false;  // [i,j] 不构成回文串
                else { 
   
                	// 等价 if (len < 3) 因为只有两个数字的话，f[i+1][j-1] 直接交换位置...
                    if (j - i < 3) f[i][j] = true;  // [i,j] 长度小于等于 2 只要s[i]==s[j]就构成回文串
                    else f[i][j] = f[i + 1][j - 1]; // 可能构成回文串，取决于 s[i+1:j-1] 是否能构成回文串
                }
                if (f[i][j] && j - i + 1 > mx) { 
   
                    mx = j - i + 1;
                    l = i;
                }
            }
        }
        return s.substr(l, mx);
    }
};