leetcode——5.最长回文子串

我的程序： class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if s==‘‘:
            return ‘‘
        if len(s)==1:
            return s
        res=[]
        for i in range(len(s)):
            c=s[i:].count(s[i])
            if  c !=1:
                b=s[::-1].index(s[i])
                j=len(s)-b-1
                if s[i:j+1]==s[i:j+1][::-1] and i!=j:
                    res.append(s[i:j+1])
                else:
                    c-=1
                    t=s[i:j]
                    if len(t)==2:
                        if t[0]==t[1]:
                            res.append(t)
                            break
                        else:
                            break
                    b=t[::-1].index(t[0])
                    j=len(t)-b-1
                    if t[:j+1]==t[:j+1][::-1] and j!=0:
                        res.append(t[:j+1])
                    c-=1
                    while c>1:
                        t=s[i:i+j]
                        if len(t)==2:
                            if t[0]==t[1]:
                                res.append(t)
                                break
                            else:
                                break
                        b=t[::-1].index(t[0])
                        j=len(t)-b-1
                        if t[:j+1]==t[:j+1][::-1] and j!=0:
                            res.append(t[:j+1])
                        c-=1
        if len(res)==0:
            return s[0]
        if len(res)==1:
            return res[0]
        m=max(len(res[i]) for i in range(len(res)))
        for i in range(len(res)):
            if len(res[i])==m:
                return res[i]

执行用时 :2192 ms, 在所有 Python 提交中击败了50.51%的用户 内存消耗 :115.1 MB, 在所有 Python 提交中击败了5.06%的用户   虽然好不容易用俩小时左右做出来了，但是感觉还是有地方很啰嗦。

执行用时为 20 ms 的范例
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """ 　　　　　if len(s) < 2 or s == s[::-1]:  　　　　　　　　return s 

        length = 1

        even_medium = 0
        even_left = 0
        for i in range(len(s) - 1):
            if i - even_left >= 0 and s[i - even_left] == s[i + 1]:
                substring = s[i - even_left: i + 2]
                if substring == substring[: : -1]:
                    even_medium = i
                    length = even_left + 2
                    even_left = even_left + 2

        odd_medium = 0            
        half = (length + 1) // 2
        odd_left = (length + 1) // 2
        for j in range(half, len(s) - half):
            if j - odd_left >= 0 and s[j - odd_left] == s[j + half]:
                substring = s[j - odd_left: j + half + 1]
                if substring == substring[: : -1]:
                    odd_medium = j
                    length = odd_left + half + 1
                    odd_left = odd_left + 2

        if length % 2 == 0:
            return s[even_medium + 2 - length: even_medium + 2]
        else:
            if length == 1:
                return s[0]
            else:
                return s[odd_medium + half + 1 - length: odd_medium + half + 1]

分析改进：

将我的程序里面的

        if s==‘‘:
            return ‘‘
        if len(s)==1:
            return s

换成：

        if len(s) < 2 or s == s[::-1]:
            return s

 

其他的还没仔细看。。。。

——2019.10.11

查看更多关于leetcode——5.最长回文子串的详细内容...