最长回文子串——从暴力枚举到中心扩展

一、题目

给定字符串 s，找到其中最长的回文子串。

例如：

s = "babad"

结果可以是：

"bab"

或者：

"aba"

---

二、暴力法：枚举所有子串

最直接的思路：

枚举子串
  ↓
判断这个子串是不是回文
  ↓
是 → 更新最长长度

判断回文也很简单：

左右两个指针向中间移动

代码

// 判断 s[left] ~ s[right] 是否为回文
bool isPalindrome(char *s, int left, int right)
{
    while (left < right)
    {
        // 两端字符不同 → 一定不是回文
        if (s[left] != s[right])
            return false;

        left++;
        right--;
    }

    return true;
}

char* longestPalindrome(char* s)
{
    int n = strlen(s);

    // 空串或单字符本身就是回文
    if (n < 2)
    {
        char *res = malloc(n + 1);
        strcpy(res, s);
        return res;
    }

    int start = 0;
    int max_len = 1;

    // i：子串左端点
    for (int i = 0; i < n; i++)
    {
        // j：子串右端点
        for (int j = i + 1; j < n; j++)
        {
            // 判断 s[i] ~ s[j] 是否为回文
            if (isPalindrome(s, i, j))
            {
                int len = j - i + 1;

                // 找到更长的回文，记录起点和长度
                if (len > max_len)
                {
                    max_len = len;
                    start = i;
                }
            }
        }
    }

    // 申请空间保存最终答案
    char *result = malloc(max_len + 1);

    strncpy(result, s + start, max_len);
    result[max_len] = '\0';

    return result;
}

为什么这种写法容易把人绕晕？

因为同时存在：

i      → 枚举左端点
j      → 枚举右端点
left   → 判断回文的左指针
right  → 判断回文的右指针

实际上是：

两层循环枚举子串
        +
一层循环判断回文

所以时间复杂度：

O(n³)

但它的优点是：

逻辑最直白，比较容易保证正确。

---

三、中心扩展法

暴力法的问题是：

先找出所有子串，再判断是不是回文。

但回文有一个非常明显的性质：

回文是关于中心对称的。

所以可以反过来：

确定一个中心
    ↓
向左右扩展
    ↓
两边相同 → 继续
两边不同 → 停止

例如：

    b a b
      ↑
     中心

从 a 开始向两边扩展：

a
↓
b a b
↓
继续扩展

---

四、为什么要考虑两个中心？

回文有两种：

奇数长度

例如：

"bab"

中心是：

b a b
  ↑

中心是一个字符：

left = i;
right = i;

偶数长度

例如：

"abba"

中心在两个字符之间：

a b | b a
    ↑

所以：

left = i;
right = i + 1;

因此每个位置都要尝试两次：

expand(s, i, i);       // 奇数
expand(s, i, i + 1);   // 偶数

---

五、中心扩展代码

// 从中心向两边扩展
// 返回以 left、right 为中心能够得到的回文长度
int expand(char *s, int left, int right, int n)
{
    while (left >= 0 &&
           right < n &&
           s[left] == s[right])
    {
        // 两边相同，继续向外扩展
        left--;
        right++;
    }

    // 循环结束时：
    // left、right 已经多走了一步
    //
    // 真正的回文范围：
    // left + 1 ~ right - 1
    //
    // 长度：
    // (right - 1) - (left + 1) + 1
    // = right - left - 1
    return right - left - 1;
}

char* longestPalindrome(char* s)
{
    int n = strlen(s);

    if (n < 2)
    {
        char *res = malloc(n + 1);
        strcpy(res, s);
        return res;
    }

    int start = 0;
    int max_len = 1;

    for (int i = 0; i < n; i++)
    {
        // 奇数长度回文
        int len1 = expand(s, i, i, n);

        // 偶数长度回文
        int len2 = expand(s, i, i + 1, n);

        // 当前中心得到的最长回文
        int len = len1 > len2 ? len1 : len2;

        // 更新全局最长回文
        if (len > max_len)
        {
            max_len = len;

            // 根据中心 i 和长度计算起始位置
            start = i - (len - 1) / 2;
        }
    }

    char *result = malloc(max_len + 1);

    strncpy(result, s + start, max_len);
    result[max_len] = '\0';

    return result;
}

---

六、中心扩展最关键的代码

其实整道题真正需要理解的就这一段：

while (left >= 0 &&
       right < n &&
       s[left] == s[right])
{
    left--;
    right++;
}

三个条件：

left >= 0

防止数组左边越界。

right < n

防止数组右边越界。

s[left] == s[right]

保证当前仍然是回文。

只要三个条件同时成立：

继续向两边扩展

一旦有一个不成立：

停止

---

七、start = i - (len - 1) / 2 怎么来的？

这行代码的作用是：

已知回文中心 i 和回文长度 len，计算回文子串的起始下标 start。

关键在于：中心扩展时，i 表示的是当前枚举到的中心位置。

例子一：奇数长度回文 "aba"

假设字符串是：

s = "caba"

下标如下：

下标： 0 1 2 3
字符： c a b a

当 i = 2 时，以 s[2]，也就是字符 'b' 为中心进行扩展：

c a b a
    ↑
   中心

先比较：

s[2] 和 s[2]

相同，继续向两边扩展：

s[1] = 'a'
s[3] = 'a'

两边也相同，所以得到回文：

"a b a"

它的长度是：

len = 3

回文中心到起点之间的距离是：

(len - 1) / 2
= (3 - 1) / 2
= 1

因此：

start = i - (len - 1) / 2
      = 2 - 1
      = 1

所以回文子串从下标 1 开始：

s[1] ~ s[3] = "aba"

---

例子二：奇数长度回文 "abcba"

假设：

s = "abcba"

下标如下：

下标： 0 1 2 3 4
字符： a b c b a

当 i = 2 时，以字符 'c' 为中心：

a b c b a
    ↑

向两边扩展：

第一次：s[2] 和 s[2] → c == c
第二次：s[1] 和 s[3] → b == b
第三次：s[0] 和 s[4] → a == a

得到完整回文：

"abcba"

此时：

len = 5

中心到起点的距离是：

(len - 1) / 2
= (5 - 1) / 2
= 2

所以：

start = 2 - 2
      = 0

回文从下标 0 开始，正好是：

s[0] ~ s[4] = "abcba"

---

例子三：偶数长度回文 "abba"

偶数长度回文的中心不是某一个字符，而是两个字符之间的缝隙。

假设：

s = "zabba"

下标如下：

下标： 0 1 2 3 4
字符： z a b b a

当 i = 2 时，偶数回文的中心是：

left = i;
right = i + 1;

也就是比较：

s[2] 和 s[3]

对应字符：

z a b | b a
      ↑
     中心

向两边扩展：

s[2] = 'b'，s[3] = 'b' → 相同
s[1] = 'a'，s[4] = 'a' → 相同

得到回文：

"abba"

它的长度是：

len = 4

此时 i = 2，代入公式：

start = i - (len - 1) / 2
      = 2 - (4 - 1) / 2
      = 2 - 3 / 2
      = 2 - 1
      = 1

这里的 / 是 C 语言中的整数除法，所以：

3 / 2 = 1

因此：

start = 1

回文子串就是：

s[1] ~ s[4] = "abba"

---

为什么奇数和偶数可以用同一个公式？

对于奇数长度回文：

i

正好是回文中间的字符。

对于偶数长度回文：

i

表示中心右侧第一个字符的位置。

虽然两种情况下中心的含义略有不同，但使用整数除法后，下面这个公式都能正确算出起点：

start = i - (len - 1) / 2;

可以简单记成：

回文起点 = 中心位置 - 中心到左端点的距离

其中：

中心到左端点的距离 = (len - 1) / 2

所以最终就是：

start = i - (len - 1) / 2;

例如：

奇数长度 3：中心 i = 2，start = 2 - 1 = 1
偶数长度 4：中心 i = 2，start = 2 - 1 = 1
奇数长度 5：中心 i = 2，start = 2 - 2 = 0

只要记住中心扩展时的两种调用：

expand(s, i, i, n);       // 奇数长度
expand(s, i, i + 1, n);   // 偶数长度

以及统一的起点计算：

start = i - (len - 1) / 2;

就可以正确截取最长回文子串。

---

八、复杂度

暴力枚举

枚举所有子串：O(n²)
判断每个子串是否回文：O(n)

所以：

时间复杂度：O(n³)
空间复杂度：O(1)

中心扩展

每个位置最多向两边扩展：

时间复杂度：O(n²)
空间复杂度：O(1)

---

九、两种方法怎么选？

暴力法
↓
思路最直观
↓
代码容易理解
↓
O(n³)

中心扩展
↓
利用回文的对称性
↓
直接从中心向两边找
↓
O(n²)

笔试时如果时间紧：

先保证暴力法能写对，再考虑中心扩展。

面试时被要求优化：

从 O(n³) 优化到 O(n²)，讲中心扩展即可。

---

十、这道题真正需要记住的东西

不要死记整段代码，记住这个模型：

回文
 ↓
具有中心
 ↓
枚举中心
 ↓
左右扩展
 ↓
比较 s[left] 和 s[right]
 ↓
相等继续，不等停止

而中心有两种：

奇数：i, i
偶数：i, i + 1

核心循环：

while (left >= 0 &&
       right < n &&
       s[left] == s[right])
{
    left--;
    right++;
}

这就是中心扩展法。