5. 最长回文子串 Longest Palindromic Substring

(1) 暴力求解

class Solution:
    def longestPalindrome(self, s: str) -> str:
        maxlen=0
        result=''
        for i in range(len(s)):
            for j in range(i,len(s)+1):##注意首尾坐标
                if s[i:j]==s[i:j][::-1]:
                    if j-i>maxlen:
                        maxlen=j-i
                        result=s[i:j]
                        #print(result)
        return result    

5. 最长回文子串 Longest Palindromic Substring

(2)动态规划,改进(1)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        arr=[[0]*n for i in range(n)]
        maxlen=0
        result=''

        for j in range(n):
            for i in range(j+1):
                if (j-i<2 or arr[i+1][j-1]==1) and s[i]==s[j]:
                    arr[i][j]=1
                if arr[i][j] and j-i+1>maxlen:
                    maxlen=j-i+1
                    result=s[i:j+1]
        return result

5. 最长回文子串 Longest Palindromic Substring

3. 找到回文串的中心,然后向两边扩展即可。

中心位置我们要奇偶分开考虑,如果字符串长度是奇数的话,中心就只有一个元素;如果字符串是偶数的话,那么中心是两个元素。

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

        maxlen=0
        result=''
        for i in range(n):
            len1=expandAroundCenter(i,i)#中间是奇数
            len2=expandAroundCenter(i,i+1)#中间是偶数
            mlen=max(len1,len2)
            if mlen>maxlen:
                maxlen=mlen
                result=s[i-(maxlen-1)//2:i+maxlen//2+1]
                
        return result

5. 最长回文子串 Longest Palindromic Substring

4. 先确定回文串的右边界i,然后以右边界i向左找回文串。假设在i之前的最长回文子串长度是l,此时我们需要分别检查i+1左侧字符串长度为l+2l+1子串是不是回文串。如果l+2是回文串,那么字符串的最大长度变成l+2,对于l+1同理。

5. 最长回文子串 Longest Palindromic Substring

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        if (len(s)<2) or s==s[::-1]:
            return s
        
        maxlen=1
        left=0
        for i in range(1,len(s)):
            s2=s[i-maxlen-1:i+1]   #check L+2
            s1=s[i-maxlen:i+1]  #check L+1
            if i-maxlen-1>=0 and s2==s2[::-1]:
                left=i-maxlen-1
                maxlen+=2
            elif i-maxlen>=0 and s1==s1[::-1]:
                left=i-maxlen
                maxlen+=1
            
        return s[left:left+maxlen]
    

5. 最长回文子串 Longest Palindromic Substring

5. 最长回文子串 Longest Palindromic Substring5. 最长回文子串 Longest Palindromic Substring weixin_45405128 发布了163 篇原创文章 · 获赞 90 · 访问量 6255 私信 关注
上一篇:5. 最长回文子串_Longest Palindromic Substring


下一篇:【转】动态规划:最长递增子序列Longest Increasing Subsequence