题目: 最长回文子串

最长回文子串

难度：中等

给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

 

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

分析

寻找最优解的题目都可以用暴力破解的方式进行解题。

暴力破解

暴力破解首先需要找出所有的字符子串，找出所有的字符子串需要两层循环，外层循环表示子串的起始位置，内层循环表示子串的结束位置。

因为题目求解最长回文子串，所以需要判断这些子串是否回文串，判断过程需要遍历该子串。

所以暴力破解的时间复杂度是O（n³）。

动态规划

最长回文子串是一个子结构问题，如果a_ma_m+1a...a_n-1a_n是一个回文串a_m+1a...a_n-1也同样是回文串。所以此类问题可以使用动态规划法解决。

动态规划方法中需要首先确定状态的变量，子串的两个下标明显是影响状态的变量，状态就是回文子串的长度。

确定状态方程往往思考当前状态如何从上一个状态变迁着手，例如当前子串如果是回文串，那么去掉头尾的字符串一定也是回文子串。所以当过f(i，j)>0，也就是i，j中间的字符串是回文子串的时候，如果i-1位置的字符和j+1位置的字符相等，则f(i-1，j+1)等于f(i，j)+2。

回文子串确定边界条件需要分两种情况考虑，如果子串是偶数位，那么边界就是连续的两个字符串相等的情况，如果字符串是奇数位，那么字符串中间位置的字符需要将状态置为1。

综合状态转移方程和边界条件，最长回文子串的公式如下：$f(i,j)={\begin{cases}f(i+1,j-1)+2,a_{i}=a_{j}\\1,i=j\\2,j=i+1\And a_{i}=a_{j}\end{cases}}$

构造法

利用最长回文子串的对称性，将回文字符串往两侧延伸直到不再是回文串为止就可以得到该中心位置的最长回文串，此类的中心位置可以是一个字符也可以是两个字符，如果中心位置是一个字符，最终的回文串是奇数，如果是两个字符，则最终的最长回文子串是偶数位。

所以构造法可以循环该字符串，先将当前位值往两侧延伸寻找奇数位的最长回文串，之后再将当前位置和当前位置加一作为中心位置寻找偶数位的最长回文串，最后比较所有的回文串的长度，得处最长回文串。

构造法的时间复杂度是O（n²）。

马拉车

采用马拉车算法可以将时间复杂度降至O（n）。

解题

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        int maxlenth = 0;
        int left = 0;
        int right = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        dp[i][j] = true;
                    }
                }
                if (dp[i][j] && j - i + 1 > maxlenth) {
                    maxlenth = j - i + 1;
                    left = i;
                    right = j;
                }
            }

        }
        return s.substr(left, right - left + 1);
    }
};