最长的回文子串

[编程题]最长的回文子串

热度指数：20172 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

找出给出的字符串S中最长的回文子串。假设S的最大长度为1000，并且只存在唯一解。

示例1

输入

"abcba"

输出

"abcba"

算法知识视频讲解

Python

黄沙遮天

本题主要采用的方法是长短指针，有两个临界点需要考虑，一是第一次出现回文子串，然后r继续增长，二是直到不符合回文子串时，就让l加1.从这两种状态中找出最长的回文子串。另外需要注意的就是在循环结束后，最后的字符串还没处理，可能不是回文字符串，也可能不是。

class Solution:
    def longestPalindrome(self , s ):
        # write code here
        l,r=0,0
        maxstr=''
        flag=0
        while(r!=len(s)):
            temstr=''
            temstr=s[l:r]
            if s[l:r]!=temstr[::-1] and flag==0:
                r+=1
            elif s[l:r]==temstr[::-1] and len(s[l:r])>=2 and flag==0:
                if len(maxstr)<len(s[l:r]):
                    maxstr=s[l:r]
                flag=1
                r+=1
            elif s[l:r]==temstr[::-1] and flag==1:
                if len(maxstr)<len(s[l:r]):
                    maxstr=s[l:r]
                r+=1
            elif s[l:r]!=temstr[::-1] and flag==1:
                l+=1
                if len(maxstr)<len(s[l:r]):
                    maxstr=s[l:r]
            else:
                r+=1
        temstr=s[l:r]
        if s[l:r]==temstr[::-1]:
            if len(maxstr) < len(s[l:r]):
                maxstr = s[l:r]
        elif s[l:r]!=temstr[::-1]:
            while(l<r and s[l:r]!=temstr[::-1]):
                l+=1
                temstr=s[l:r]
            if  s[l:r]==temstr[::-1]:
                if len(maxstr) < len(s[l:r]):
                    maxstr = s[l:r]
        return maxstr

发表于 2020-08-25 15:23:29 回复(1)

Python

Liiy

#python实现
class Solution:
    def longestPalindrome(self , s )-> str:
        # write code here
        res = ''
        for i in range(len(s)):
            start =  max(0,i-len(res)-1)
            temp = s[start:i+1]
            if temp == temp[::-1]:
                res = temp
            else:
                temp = temp[1:]
                if temp == temp[::-1]:
                    res = temp
        return res

发表于 2020-08-10 00:05:05 回复(0)