2019-05-1 LeetCode35. 最长回文子串

暴力，所有子串，通过不了

class Solution:
    def longestPalindrome(self, s: str) -> str:
        result=''
        maxL=0
        for i in range(len(s)):
            for j in range(i,len(s)):
                isPal=self.checkPal(s[i:j+1])
                if(isPal and j-i+1>maxL):
                    result=s[i:j+1]
                    maxL=j-i+1  # 这里忘了重新赋值，卡住了
        return result

    def checkPal(self,s:str)-> bool:
        for i in range(len(s)//2):
            if(s[i]!=s[len(s)-1-i]):return False
        return True

参考动态规划的思路，自底向上写，偶尔能通过？4112毫秒，不懂。40分钟

class Solution:
    def longestPalindrome(self, s: str) -> str:
        result=''
        # matrix=np.zeros((len(s),len(s)))
        matrix=[ [0 for j in  range(len(s))] for i in range(len(s))]  #不能用numpy，有点头疼
        # print(matrix)
        maxL=0
        l,r=0,0
        for i in range(len(s)):
            matrix[i][i]=1
            maxL=1
        for i in range(len(s)-1):
            if(s[i]==s[i+1]):
                matrix[i][i+1]=1;
                maxL=2
                l,r=i,i+1
        for t in range(2,len(s)):
            for i in range(len(s)-t): # 边界条件按照特例来想，这里有点卡
                if(s[i]==s[i+t] and matrix[i+1][i+t-1]!=0):
                    matrix[i][i+t]=2  # 妈的写了==号要了命，这里最卡
                    if(maxL<t+1):
                        maxL = t + 1
                        l,r=i,i+t
        return s[l:r+1]

使用中心向外扩展方法快很多，虽然同样是o(n^2 )可以说是比90%的人快