5. 最长回文子串

引流：人工智能领域专栏

题目：

给你一个字符串?s，找到?s?中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

【解题思路】

?不要多想，本题就用动态规划解决。既然是动态规划，那么就要考虑动态规划数组如何建立，一般我们都会建立一个二维数组用于存储动态规划的中间过程，而在这之前，要充分挖掘题目的规律。本题中，对于一个字符串，想要让它回文，无非就是镜像首尾要一样，例如aa、aba、abccba等，所以

第一步：定义一个二维dp数组，数组里初始值全为False；

第二步：数组中什么时候值为True呢？既然存在首尾相同的条件，那么就需要定义两个指针，一个指针不断像字符串后遍历，另一个指针在前一个指针所在的每一个位置前遍历，直到遍历到与前一个指针相遇；

第三步：在第二步中，每次遍历都考虑两件事，一是两个指针所指向的字符是否相同，如果相同，那么这两个字符所裹挟的字符串很有可能是回文串，具体怎么判定呢？拿`aacabaccba`来举例，如果相邻的两个字符一样，如“aa”，那它肯定是回文串，如果如果两个一样的字符不相邻但中间只裹挟一个字符，如“aca”，那它也必然是回文串，除此之外，其它的情况就不一定了；所以我们要判断的条件之一是首尾两个字符是否相同，条件之二是看相同的首尾两个字符所组成的子串长度是否小于等于3，如果是，那么就让dp数组对应的位置为True；

第四步：第三步中，如果满足条件一但不满足条件二呢？由于本题解题思路是动态规划，所以当首尾相同字符裹挟的字符不止一个时，那么只需要首尾字符同时向内缩一个再判断此时的子串是否为回文串就行了，因为此时的子串在之前的遍历中肯定是已经判断过了，如果此时的字符串为回文串，那么原首尾字符组成的子串也必然是回文串。还以`aacabaccba`举例，假设此时我们遍历到首尾字符所组成的子串为`cabac`，c和c相同，但`cabac`长度超过3，所以向内缩为`aba`，这个时候我们只需要判断`aba`是否为回文即可确定`cabac`是否为回文，而`aba`在之前肯定已经判断过了，在哪呢？就在dp数组里存着呢！所以找dp[left+1][right-1]所对应的值是不是True就行了。

综上所述，代码如下：

def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return s
        dp = [[False]*len(s) for _ in range(len(s))]
        start, end = 0, 0
        maxlength = 0
        for right in range(1, len(s)):
            for left in range(right):
                if s[right] == s[left] and (right-left<=2 or dp[left+1][right-1]):
                    dp[left][right] = True
                    if right - left > maxlength:
                        maxlength = right - left
                        start = left
                        end = right
        return s[start:end+1]