最长回文子串

在计算机科学中，最长回文子串或最长对称因子问题是在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串不一定是唯一的，比如“abracadabra”，没有超过3的回文子串，但是有两个回文子串长度都是3: “aba” 和 “aca”。

在一些应用中，我们需要求出全部的极大回文子串（不被其他回文子串包含的回文子串）。

问题描述

LeetCode 链接：https://leetcode-cn.com/problems/longest-palindromic-substring/description

algorithms
Medium (28.04%)
Likes: 1617
Dislikes: 0
Total Accepted: 163.5K
Total Submissions: 582.9K
Testcase Example: ‘“babad”‘

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：
输入: “cbbd”
输出: “bb”

解题思路

官方给出了5种解决算法，分别是最长公共子串、暴力法、动态规划、中心扩展算法、Manacher 算法。

此文仅提供时间复杂度为O(n^2)的解决方法——中心扩展算法。

我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n-1 个这样的中心。

你可能会问，为什么会是 2n−1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如 “abba” 的中心在两个 ‘b’ 之间）。

Golang 实现

func longestPalindrome(s string) string {

      if len(s) < 2 { // 如果字符串小于2，则本身就是最大回文子串
        return s 
    }

    start, end := 0, 0 // 记录最大回文子串起始、结束位置
    for i := 0; i < len(s); i++ { // 以 i，i+1 为中心向两侧展开
        len1 := expandAroudCenter(s, i, i)
        len2 := expandAroudCenter(s, i, i+1)
        len3 := max(len1, len2) // max 函数请自行实现
        if len3 > end-start {
            start = i - (len3-1)/2
            end = i + len3/2
        }
    }

    return s[start:end+1]
}

// 从中心位置开始寻找最长回文子串，返回最长子串长度
func expandAroudCenter(s string, left int, right int) int {

    for left >= 0 && right < len(s) && s[left] == s[right] {
        left --
        right ++
    }
    return right - left - 1
}