题目

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

示例：

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

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

输入：s = "a"
输出："a"

输入：s = "ac"
输出："a"

解答 & 代码

解法一：动态规划

想法：

如果一个子串长度为 1，则肯定是回文子串
如果一个子串长度为 2，若首尾元素相同，则是回文子串，否则不是
如果一个子串长度大于 2，若去掉首尾元素后剩余的中间子串是回文子串并且首尾元素相同，则是回文子串，否则不是回文子串

动态规划：

二维数组 dp，dp[i][j] 代表子串 s[i,...,j] 是否为回文子串

状态转移方程：

dp[i][j]     = true                                                            , if len == 1 (len = i - j + 1) // 可当作初始化
                  = s[i] == s[j]                                            , if len == 2
                  = dp[i + 1][j - 1] && s[i] == s[j]    , if len > 2

初始化：长度为 1 的子串是回文子串，因此 dp[i][i] = true

时间复杂度 [中等] 5. 最长回文子串 - 图1 ，空间复杂度 [中等] 5. 最长回文子串 - 图2

class Solution {
public:
    string longestPalindrome(string s) {
        int sLen = s.size();
        if(sLen <= 1)        // 特殊情况：如果长度小于等于一，返回字符串本身
            return s;

        int maxLeft = 0;    // 最大回文子串的左边界（含）
        int maxRight = 0;    // 最大回文子串的右边界（含）

        // 动态规划 dp 数组，dp[i][j] 代表子串 s[i,...,j] 是否为回文子串
        vector<vector<bool>> dp(sLen, vector<bool>(sLen, false));
        for(int i = 0; i < sLen; ++i)    // 初始化：长为 1 的子串肯定是回文子串
            dp[i][i] = true;

        // 状态转移，只需求 dp 数组右上三角各位置的值（下半三角 i<j 本身不合法）
        // 状态转移方程：
        // dp[i][j] = s[i] == s[j]                        , if len == 2
        //            = dp[i + 1][j - 1] && s[i] == s[j]    , if len > 2
        // 因此状态 dp[i][j] 和第 i+1 行的 j-1 列有关，就不能外层先遍历左边界 i，而是先遍历 len
        for(int len = 2; len <= sLen; ++len)    // 遍历子串长度
        {
            for(int i = 0; i < sLen; ++i)        // 遍历左边界位置
            {
                int j = i + len - 1;            // 右边界位置
                if(j >= sLen)                    // 右边界越界则退出当前循环（左边界再增大更加越界）
                    break;

                // 状态转移
                if(len == 2)                    
                    dp[i][j] = s[i] == s[j];
                else
                    dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];

                // 更新最大子串的左右边界
                if(dp[i][j] == true && len > maxRight - maxLeft + 1)
                {
                    maxLeft = i;
                    maxRight = j;
                }
            }
        }

        return s.substr(maxLeft, maxRight - maxLeft + 1);
    }
};

执行结果：

执行结果：通过

执行用时：824 ms, 在所有 C++ 提交中击败了 20.91% 的用户
内存消耗：29.5 MB, 在所有 C++ 提交中击败了45.54% 的用户

解法二：中心扩展算法

牛客网：NC17 最长回文子串
题目略有不同，不用返回最长回文子串，只需返回最长回文子串长度

时间复杂度

空间复杂度 O(N)

class Solution {
public:
  int getLongestPalindrome(string A, int n) {
      int maxLen = 0;
      // 遍历数组，分别以每个元素为回文子串中心，向两边扩展，求长度
      for(int i = 0; i < n; ++i)
      {
          // 以每个元素为中心都有两种情况

          // 回文子串长度为奇数，该元素 A[i] 就是中心
          int left = i - 1;
          int right = i + 1;
          while(left >= 0 && right < n && A[left] == A[right])
          {
              --left;
              ++right;
          }
          if(right - left - 1 > maxLen)
              maxLen = right - left - 1;

          // 回文子串长度为偶数，A[i] 和 A[i+1] 是中心
          left = i;
          right = i + 1;
          while(left >= 0 && right < n && A[left] == A[right])
          {
              --left;
              ++right;
          }
          if(right - left - 1 > maxLen)
              maxLen = right - left - 1;
      }
      return maxLen;
  }
};

``` 执行结果：通过

执行用时：3 ms, 在所有 C++ 提交中击败了 75.73% 的用户内存消耗：572 KB, 在所有 C++ 提交中击败了40.86% 的用户 ```