最长回文子串

本节学习一个经典的算法问题--最长回文子串问题,这是一个二维动态规划问题.

问题描述:

给定一个字符串s,找到s中最长的回文子串.回文子串即从头或末尾读起是完全相同的字符串.

思路解析:

首先考虑子问题是社么?对于一个回文子串来说,如abbccbba,从头部和尾部去掉相同数量的字符,中间部分依然是一个回文子串;由此可见,对于一个回文子串来说,其子结构就是其中间部分仍为回文子串.我们可以用一个二维数组来表示本字符串的两位之间是否为回文子串,在初始化时默认只有二维数组的对角线上是True,其余位置默认是False,初始化代码的数组如下:

s变量:表示输入变量,输入原始字符串

dp变量:定义二维数组,用于保存字符串两位之间是否为回文子串,数组内每个数据类型为布尔类型

通过分析,我们可以得到该问题的递推关系.当判断出s[i]=s[j]时,就继续判断dp[i-1][j+1]是否为回文子串,如果是,那么s[i]到s[j]是回文子串,再更新dp[i][j]为True

由于在判断第i-j位之间是不是回文子串之前,要求i+1到j-1位不是回文子串,因此在遍历字符串s的过程中,从后向前遍历.因此遍历代码如下:

i=len(s)-2
while(i>=0):
    j = i+1

这个遍历中的i是从尾部向前,j是从i+1到字符串尾部逐个判断.由于题目中还有最长回文子串的要求,因此需要一边搜寻回文子串一边判断是否为最长的回文子串,当确认s[i]到s[j]是回文子串之后,需要对其长度与目前为止最长回文子串进行对比,如果更长,则对目前最长回文子串的长度与首位进行更新.那么,完整的代码如下:

def longestPalindrome(s):
    # 初始化左右指针，用于记录最长回文子串的边界
    right = left = 0
    # 初始化动态规划数组，用于存储子串是否为回文
    dp = []
    # 填充dp数组，每个字符自身都是一个回文子串
    for i in range(len(s)):
        dp.append([False]*len(s))
        dp[i][i] = True  # 单个字符总是回文

    # 从字符串的倒数第二个字符开始，向两边扩展
    i = len(s)-2
    while i >= 0:
        j = i + 1
        # 从当前位置开始，向两边扩展检查回文
        while j < len(s):
            # 当前位置和j位置的字符相同，且(i+1, j-1)是回文或者i和j相邻（即长度为2的回文）
            dp[i][j] = s[i] == s[j] and (dp[i+1][j-1] or j-i == 1)
            # 如果dp[i][j]为True，且当前回文子串长度大于之前记录的最长回文子串长度，则更新左右指针
            if dp[i][j] and right - left < j - i:
                right = j
                left = i
            j += 1
        i -= 1
    return s[left:right+1]  # 返回最长回文子串