leetcode——5.最长回文子串

1. 简介

本文将介绍LeetCode第5题“最长回文子串”的解题思路和具体实现。给定一个字符串s，找到s中的最长回文子串。回文串是正读和倒读都相同的字符串。

2. 解题思路

2.1 暴力法

最简单直接的方法就是枚举所有可能的子串，并依次判断每个子串是否为回文串。使用两层循环，外层遍历子串的起始位置，内层遍历子串的长度。然后通过判断起始位置和长度来获取子串，并判断该子串是否为回文串。

def is_palindrome(s):
    return s == s[::-1]
def longest_palindrome(s):
    n = len(s)
    if n < 2:
        return s
    
    res = ""
    max_len = 0
    
    for i in range(n - 1):
        for j in range(i + 1, n):
            if is_palindrome(s[i:j + 1]) and j - i + 1 > max_len:
                res = s[i:j + 1]
                max_len = j - i + 1
    
    return res

该方法的时间复杂度为O(n^3)，其中n为字符串s的长度。

我们可以发现，在判断子串是否为回文串时，可以利用已有的信息进行优化。例如，当判断aba是否为回文串时，如果a不等于b，那么根据回文串的性质，aba肯定不是回文串。因此，对于每一个子串，如果左右两边的字符不相等，我们可以直接跳过该子串。

2.2 中心扩展法

在暴力法的基础上，我们可以继续进行优化。如果我们从左到右遍历字符串s，依次以每个字符作为中心，同时向两边扩展，判断扩展过程中的子串是否为回文串。这样的方法可以大大减少判断回文串的次数。

def longest_palindrome(s):
    n = len(s)
    if n < 2:
        return s
    
    start, end = 0, 0
    
    def expand_around_center(left, right):
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1
    
    for i in range(n):
        len1 = expand_around_center(i, i)
        len2 = expand_around_center(i, i + 1)
        length = max(len1, len2)
        
        if length > end - start:
            start = i - (length - 1) // 2
            end = i + length // 2
    
    return s[start:end + 1]

该方法的时间复杂度为O(n^2)，其中n为字符串s的长度。

通过从左到右遍历字符串s的方式，可以保证找到的回文子串是最长的。具体实现时，我们需要定义一个辅助函数expand_around_center，该函数为以left和right为中心向两边扩展，并返回扩展的长度。在每次遍历时，分别计算以当前字符为中心或以当前字符和下一个字符的中间位置为中心的回文串长度，并更新最长回文串的起始位置和结束位置。

3. 测试案例

以下是本题的几个测试案例及正确结果：

4. 总结

本文介绍了LeetCode第5题“最长回文子串”的解题思路和实现方法。通过暴力法和中心扩展法两种方法，我们可以找到给定字符串的最长回文子串。对于暴力法，我们可以通过剪枝的方式进行优化，大大减少判断回文串的次数；而中心扩展法则充分利用了回文串的对称性，减少了遍历的次数。