leetcode 5 最长回文子串

双指针法
通过遍历中心值（字符串中的每一个值），左右指针分别移动判断是否会形成回文字符串，同时记录最大长度的回文字符串。

class Solution:
    def longestPalindrome(self, s: str) -> str:

        size = len(s)
        # 特殊处理
        if size == 1:
            return s
        maxlen=0
        start=0
        length=1

        for i in range(size):
            left=i-1
            right=i+1
            while left>=0 and s[left]==s[i]:
                print(s[i])
                length+=1
                left-=1
            while right<size and s[right]==s[i]:
                print(s[i])
                length+=1
                right+=1
            while left>=0 and right<size and s[left]==s[right]:
                print(s[i])
                length+=2
                left-=1
                right+=1
            if  length>maxlen:

                maxlen=max(maxlen,length)
                start=left
            length=1

        return s[start+1:start+maxlen+1]

通过动态规划方法，通过枚举字符串的首尾字符，主要是尾字符从1到len(s),长度在2-3的，如果首尾字符相同，那么将动态规划表中填入True(初始化为False),如果长度长于此的，那么就先判断首尾字符，在判断中间字符串。最后需要记录长度，和初始值。
通过初始值和长度来得到最终的结果。

class Solution:
    def longestPalindrome(self, s: str) -> str:

        size = len(s)
        # 特殊处理
        if size == 1:
            return s
        maxlen=1
        start=0

        dp=[[ False for _ in range(size)] for _ in range(size)]       

        for j in range(1,size):
            for i in range(j):
                if j-i<=2:
                    if s[i]==s[j]:
                        dp[i][j]=True

                else:
                    if s[i]==s[j]:
                        if dp[i+1][j-1]==True:
                            dp[i][j]=True
                if dp[i][j] == True and j-i+1>maxlen:
                    maxlen=j-i+1
                    start=i 

        return s[start:start+maxlen]

动态规划，这次遍历是通过长度，先算出长度为1的字符串在dp数组中的值，再计算长度为2，3...
对于原始方法时间复杂度O(n^2)超时，对循环条件进行改善的同时，也需要注意构建二维数组时，也是O(n^2)的时间复杂度。
需要更改成[[0]*n for _ in range(n)]

class Solution:
    def longestPalindrome(self, s: str) -> str:

        size = len(s)
        # 特殊处理
        if size == 1:
            return s
        ans=""

        dp=[[ False ]*size for _ in range(size)]



        for l in range(1,size+1):
            for i in range(size-l+1):
                j=i+l-1


                if l==1:
                    dp[i][j]=True

                    if s[i]==s[j]:
                        dp[i][j]=True

                else:
                    if s[i]==s[j]:
                        if dp[i+1][j-1]==True:
                            dp[i][j]=True

                if dp[i][j] == True and l>len(ans):
                   ans=s[i:j+1]

        return ans