HHot 100C++ 图解

5. 最长回文子串

中等 多维动态规划 3 帧动画 在力扣上做

一句话套路枚举 2n-1 个中心向两边扩(奇偶都要)

题目描述

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

 

示例 1:

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

示例 2:

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

 

提示:

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

思路

思路

解法 A(中心扩展,推荐):枚举 2n-1 个中心(n 个字符中心 + n-1 个间隙中心),向两边扩。时间 O(n^2)、空间 O(1),最好写。

「奇偶两类中心」是本题唯一容易漏的点。

解法 B(区间 DP)

dp[i][j] = s[i..j] 是否回文 = s[i]==s[j] && dp[i+1][j-1]。

遍历顺序

i 从大到小(因为依赖 i+1)。Q131 预处理回文表用的就是它。

解法 C(Manacher)

O(n),利用「已知回文的对称性」跳过重复扩展,面试基本不要求手写。

注意

答案不唯一时("babad" 的 "aba"/"bab")只要长度对即可,别在测试里写死。

对比

Q647 是「回文子串个数」(同样中心扩展,累加次数);

Q680 是「最多删一个字符」(双指针 + 失败时各试一侧)。

图解

a 0 a 1 c 2 a 3 b 4 d 5 k 6 a 7 c 8 a 9 a 10
字符串 aacabdkacaa(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/16_dp_multidim.cpp25 行
namespace lc0005 {
class Solution {
 public:
  string longestPalindrome(const string& s) {
    if (s.size() < 2) return s;
    int bestStart = 0, bestLen = 1;
    for (int c = 0; c < (int)s.size(); ++c) {
      // 两类中心都要试:奇数(以字符为中心)、偶数(以间隙为中心)
      for (int offset : {0, 1}) {
        int i = c, j = c + offset;
        while (i >= 0 && j < (int)s.size() && s[i] == s[j]) {
          --i;
          ++j;
        }
        int len = j - i - 1;  // 退出时 i、j 都多走了一步
        if (len > bestLen) {
          bestLen = len;
          bestStart = i + 1;
        }
      }
    }
    return s.substr(bestStart, bestLen);
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q5_longest_palindromic_substring9 行
lc0005::Solution s;
string r1 = s.longestPalindrome("babad");
CHECK_TRUE(r1 == "aba" || r1 == "bab");  // 两个都是正确答案
CHECK_EQ(s.longestPalindrome("cbbd"), string("bb"));
CHECK_EQ(s.longestPalindrome("a"), string("a"));
CHECK_EQ(s.longestPalindrome("ac"), string("a"));  // 长度 1,取先出现者
CHECK_EQ(s.longestPalindrome("aacabdkacaa"), string("aca"));
CHECK_EQ(s.longestPalindrome("ccc").size(), (size_t)3);  // 全同
CHECK_EQ(s.longestPalindrome("").size(), (size_t)0);

↑↓ 选择↵ 打开/ 随时唤起