最长回文子串-中等

1. 题目描述
   
2. 代码

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # pa_list = []
        pa = pa_1 = pa_2 = []
        pa_len = 0
        sl = list(s)

        #假设回文个数奇数个，从中心到两端判断
        #注意不要超出左右范围，使用for循环
        #假设回文个数偶数个，最中间两个相同，逐个两端判断
        if len(sl) > 1:
            for i in range(0,len(sl)):
                # if i % 2 != 0: #奇数
                max_len = min(i,len(sl)-i-1)
                j = 1
                while(j <= max_len):
                    if sl[i-j] == sl[i+j]:
                        # pa_list.append(sl[i - j :i + j+1])
                        if pa_len < len(sl[i - j :i + j+1]):
                            pa_len = len(sl[i - j :i + j+1])
                            pa_1 = (sl[i - j :i + j+1])
                        j = j + 1
                    else:
                        break

            for i in range(0,len(sl)-1):#i与i+1组合
                max_len = min(i, len(sl) - i - 2)
                j = 1
                if sl[i] == sl[i+1]:
                    # pa_list.append(sl[i :i + 2])
                    if pa_len < len(sl[i :i  + 2]):
                        pa_len = len(sl[i :i + 2])
                        pa_2 = (sl[i :i  + 2])
                    while(j <= max_len):
                        if sl[i-j] == sl[i+1+j]:
                            # pa_list.append(sl[i - j :i + j + 2])
                            if pa_len < len(sl[i - j :i + j + 2]):
                                pa_len = len(sl[i - j :i + j + 2])
                                pa_2 = (sl[i - j :i + j + 2])
                            j = j +1
                        else:
                            break
                if pa_1 == pa_2 ==[]:#对无回文情况，考虑返回第一个字符
                    pa_1 = pa_2 = sl[0]
        elif len(sl) == 1:
            pa_1 = pa_2 = sl
        else: pa_1 = pa_2 = []
        if (len(pa_1) > len(pa_2)) :
            pa = pa_1
        else: pa = pa_2
        pa = "".join(pa)
        return pa

分为回文是奇数个还是偶数个两种思路，要单独考虑单个字符及两个字符的情况。
3. 官方示例代码
动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        # 枚举子串的长度 l+1
        for l in range(n):
            # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置
            for i in range(n):
                j = i + l
                if j >= len(s):
                    break
                if l == 0:
                    dp[i][j] = True
                elif l == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
                if dp[i][j] and l + 1 > len(ans):
                    ans = s[i:j+1]
        return ans

中心扩展算法

class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

（和我算法的思路一致，不过将回文奇数个数当作特殊的回文偶数个数的情况）
5. 总结：不懂动态规划算法