05. 最长回文子串

题目描述

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

示例 2：

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

提示：

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

题解

解法一：暴力枚举

bool check(string s) {
  for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
    if (s[i] != s[j]) {
      return false;
    }
  }
  return true;
}

string longestPalindrome2(string s) {
  string sub;
  for (int i = 0; i < s.size(); i++) {
    for (int j = i; j < s.size(); j++) {
      std::string temp = s.substr(i, j - i + 1);
      if (check(temp)) {
        sub = sub.size() > temp.size() ? sub : temp;
      }
    }
  }
  return sub;
}

解法二：动态规划

根据回文串的特点，s[i][j] 为回文串，则 s[i+1][j-1] 也为回文串。因此我们得到状态转移方程：

dp[i][j] = dp[i+1][j-1] && s[i] == s[j]

官方给出的动态规划解法，根据子串长度 len 进行遍历，右移左边界 i ，并根据 len 和 i 倒推右边界 j。此时存在额外需要处理的两处逻辑边界：

1. 当 len < 3 时， dp[i+1][j-1] 出现翻转，手动设置 dp[i][j] 为 true;
2. j = i + len - 1 存在下标溢出，需额外判断停止循环;

此处给出优化解法，使用左右边界进行遍历，由于dp[i][j] 依赖于 dp[i+1][j-1]，因此左边界 i 应该从大到小，右边界 j 从小到大，我们从右下角开始遍历，即从左边界开始遍历，右边界逐渐右移。

string longestPalindrome3(string s) {
  if (s.size() < 2) return s;
  int maxl = s.size(), start = 0, len = 1;
  vector<vector<bool>> dp(maxl, vector<bool>(maxl, true));
  for (int i = maxl - 2; i >= 0; i--) {
    for (int j = i+1; j < maxl; j++) {
      dp[i][j] = false;
      if (s[i] == s[j]) {
        dp[i][j] = dp[i+1][j-1];
        if (dp[i][j] && len < j - i + 1) {
          start = i;
          len = j - i + 1;
        }
      }
    }
  }
  return s.substr(start,len);
}

解法三：中心扩展

枚举回文字符串中心点，由于回文字符串长度可能为奇数 1 个中心点或偶数 2 个中心点，因此我们将中心点统一扩展为 2 个，奇数时两个中心点相同，遍历过程中每次都需计算奇偶两种情况。

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        int start = 0, mx = 1;
        auto f = [&](int l, int r) {
            while (l >= 0 && r < n && s[l] == s[r]) {
                l--, r++;
            }
            return r - l - 1;
        };
        for (int i = 0; i < n; ++i) {
            int a = f(i, i);
            int b = f(i, i + 1);
            int t = max(a, b);
            if (mx < t) {
                mx = t;
                start = i - (t - 1 >> 1);
            }
        }
        return s.substr(start, mx);
    }
};

总结

1. 暴力枚举可解，但是时间复杂度为 O(n^3)，部分超长用例存在超时问题；
2. 动态规划，找到状态转移方程，回文字符串形式为关键点；
3. 动态规划解法中，根据状态转移方程优化遍历条件和顺序，减少边界判断；
4. 中心扩展算法，奇偶差异性如何统一，减少冗余计算