题目

        回文是一个正读和反读都相同的字符串，比如："aba"是回文，而"abc"不是回文。现给定一个字符串s，找出s中最长的回文子串（可能有多个最长的，找出一个即可）。

        示例 1：

输入: "babad"
输出: "bab"（"aba" 也是一个有效答案）

        示例 2：

输入: "cbbd"
输出: "bb"

暴力法

        使用暴力法求解本题非常直观，其基本思想是：检查字符串s中的所有子串，判断它们是否为回文，并记录下最长的回文子串。使用暴力法求解本题的主要步骤如下。

        1、初始化一个空字符串max_palindrome，作为最长回文子串。

        2、遍历字符串s中的所有子串，进行以下操作。

        （1）对于每个子串，检查它是否为回文。

        （2）如果该子串是回文，且长度大于已知最长回文子串的长度，则更新max_palindrome。

        3、返回max_palindrome。

        根据上面的算法步骤，我们可以得出下面的示例代码。

def longest_palindrom_substring_by_brute_force(s):
    def isPalindrome(sub):
        return sub == sub[::-1]
    
    max_palindrome = ""
    n = len(s)
    
    # 遍历所有可能的子串
    for i in range(n):
        for j in range(i, n):
            sub = s[i:j+1]
            if isPalindrome(sub) and len(sub) > len(max_palindrome):
                max_palindrome = sub
                
    return max_palindrome

s = "babad"
print(longest_palindrom_substring_by_brute_force(s))
s = "cbbd"
print(longest_palindrom_substring_by_brute_force(s))

动态规划法

        动态规划法通过构建一个二维布尔数组dp来记录子串是否为回文，dp[i][j]表示从索引i到j的子串是否为回文串。使用动态规划法求解本题的主要步骤如下。

        1、初始化一个(n+1) x (n+1)的二维布尔数组 dp，其中，n是字符串s的长度。

        2、设置边界条件。所有长度为1的子串都是回文串，即：dp[i][i] = True。

        3、设置长度为2的子串的回文条件。如果s[i] == s[j]，且j == i + 1，则dp[i][j] = True。

        4、对于长度大于2的子串，如果s[i] == s[j]，且dp[i+1][j-1]为True，则dp[i][j] = True。

        5、在构建dp的过程中，记录下最长回文子串的起始位置和长度。

        根据上面的算法步骤，我们可以得出下面的示例代码。

def longest_palindrom_substring_by_dp(s):
    n = len(s)
    if n == 0:
        return ""
    
    # 初始化dp数组
    dp = [[False] * n for _ in range(n)]
    
    # 设置边界条件
    for i in range(n):
        dp[i][i] = True
    
    start = 0
    max_length = 1
    # 设置长度为2的子串的回文条件
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start = i
            max_length = 2
    
    # 对于长度大于2的子串
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                start = i
                max_length = length
    
    # 返回最长回文子串
    return s[start:start+max_length]

s = "babad"
print(longest_palindrom_substring_by_dp(s))
s = "cbbd"
print(longest_palindrom_substring_by_dp(s))

中心扩展算法

        仔细观察回文字符串可以发现，回文中心的两侧互为镜像。而回文的中心，可以是一个字符（对应奇数个字符的回文），也可以是两个字符（对应偶数个字符的回文）。中心扩展算法的基本思想为：从给定字符串的中心点开始，向两边扩展，判断以当前中心点为中心的子串是否是回文串；如果是，则继续向两边扩展，直到无法再扩展为止。使用中心扩展算法求解本题的主要步骤如下。

        1、初始化一个空字符串max_palindrome，作为最长回文子串。

        2、遍历字符串s中的每个字符，或相邻的两个字符，作为潜在的中心。

        3、从中心开始向两边扩展，检查子串是否为回文。如果找到的回文子串长度大于已知最长回文子串的长度，则更新max_palindrome。

        4、返回max_palindrome。

        根据上面的算法步骤，我们可以得出下面的示例代码。

def longest_palindrom_substring_by_center_expansion(s):
    def expandAroundCenter(s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    max_palindrome = ""
    for i in range(len(s)):
        # 奇数长度的回文子串
        palindrome1 = expandAroundCenter(s, i, i)
        # 偶数长度的回文子串
        palindrome2 = expandAroundCenter(s, i, i + 1)
        
        # 更新最长回文子串
        if len(palindrome1) > len(max_palindrome):
            max_palindrome = palindrome1
        if len(palindrome2) > len(max_palindrome):
            max_palindrome = palindrome2
            
    return max_palindrome

s = "babad"
print(longest_palindrom_substring_by_center_expansion(s))
s = "cbbd"
print(longest_palindrom_substring_by_center_expansion(s))

总结

        暴力法需要遍历所有可能的子串（时间复杂度为O(n^2)），并对每个子串进行回文检查（时间复杂度为O(n)），故总的时间复杂度为O(n^3)。其空间复杂度为O(1)，只使用了有限的额外空间。可以看到，暴力法的效率较低，不适合处理大数据集。

        动态规划法需要遍历所有可能的子串，并构建二维数组dp，故时间复杂度为O(n^2)。其空间复杂度也为O(n^2)，因为需要一个二维数组dp来存储所有子串的回文状态。与暴力法相比，动态规划法的效率更高，但需要较多的额外空间来存储回文状态。

        使用中心扩展算法时，每个中心扩展最多可能扩展n步，此时的时间复杂度为O(n^2)。在实际应用中，中心扩展算法的平均时间复杂度通常接近O(n)。其空间复杂度为O(1)，只使用了有限的额外空间。中心扩展算法比动态规划法更快，且不需要额外的空间来存储回文状态。

💡 需要《Python面试宝典》完整源码的大佬们，可订阅专栏后，搜索微信公众号“希望睿智”私信获取。