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

大家好，又见面了，我是你们的朋友全栈君。

1. 题目来源

链接：lc5. 最长回文子串

2. 题目解析

方法一：枚举

回文串一共有两种，即长度为奇数的回文串，长度为偶数的回文串。我们可以枚举回文串的中心(偶数长度回文串假想一个中心就行了)，然后分别拿两个指针 l = i - 1，r = i + 1 向左右两边同时拓展，若 s[l]=s[r] 则，l --, r ++。一直进行该操作，直到不等或一方到达边界位置。

我们针对每一个枚举位置 i，都考虑其两种情况，即偶数，奇数都考虑一遍，取个最大的就行了。

时间复杂度：$O(n^2)$

至于本问题，还有一些非常秀的方法。dp 在这也只能达到 $O(n^2)$ 的时间复杂度，且还要开辟 dp 数组。

其中，字符串哈希+二分，貌似能够做到 $O(nlogn)$ 的时间复杂度。

至于那个，马拉车算法，之前简单看过，专门解决最长回文子串问题，时间复杂度能达到 $O(n)$，不过可拓展性非常之低。

本题采用的中心拓展思想在别的问题中也能用到~

代码：

// 暴力直接算，即中心扩散，时间复杂度为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;
    }
};

方法二：区间 dp

更新于 2021 年 4 月 16 日晚。字符串区间 dp 的题目比较少，经典有 lc 87 题，dfs 超时，区间 dp 可解，lc 87 是很难的一道题。

官方题解思路蛮不错的，三种方法都有涉及。

思路：

• f[i][j] 表示 s[i : j] 能否构成回文串。
• 当区间长度为 1 时，必然构成一个回文串，即 f[i][i] = true;。
• 字符串区间 dp 最重要的就是 枚举长度，要理解这个枚举顺序。
• 枚举长度，再枚举左边界，通过长度确定右边界坐标。
• 若右坐标合法，那么判断左右坐标对应字符是否相等，若不等则 f[i][j] 不构成回文串。否则，如果区间长度小于 3 的话，那么就直接是 f[i][j]=true，因为只有两个数字的话，f[i+1][j-1] 直接交换位置…造成状态的错误更新。否则区间长度大于等于三时，s[i : j] 首先两侧字符相等，那么 f[i][j] = f[i+1][j-1]。这两者是等价的。进行状态转移即可。

时间复杂度：$O(n^2)$
空间复杂度：$O(n^2)$

很经典的一道题目，三种解法中的任一种都是非常经典且值得学习的。中心拓展、区间 dp 都是非常常用的思想，而马拉车不常用，但它却是能 $O(n)$ 的解决该问题！日后再补吧，以前总结了，又忘了…

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);
    }
};