(Medium #5) Longest Palindromic Substring

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"

My solution

class Solution:
    def myfunc(self, s, start, end):
        condition = True
        while condition:
            if (start-1 >= 0 and end+1 < len(s)) and s[start-1] == s[end+1]:
                start = start-1
                end = end+1
            else:
                condition = False
        return start, end

    def longestPalindrome(self, s: str) -> str:
        max_len = 0
        result= ''

        if len(s)==1:
            return s[0]
        if len(s)==2:
            if s[0]==s[1]:
                return s
            else:
                return s[0]

        # center position
        for i in range(1,len(s)-1):
            if s[i-1] == s[i+1]:
                start = i-1
                end = i+1       
                start, end = self.myfunc(s, start, end)             
                sen = s[start:end+1]
                if max_len < end-start+1:
                    max_len = end-start+1
                    result = sen 
             
            if s[i-1] == s[i]:
                start = i-1
                end = i
                start, end = self.myfunc(s, start, end)
                sen = s[start:end+1]
                if max_len < end-start+1:
                    max_len = end-start+1
                    result = sen 
             
            if s[i] == s[i+1]:
                start = i
                end = i+1
                start, end = self.myfunc(s, start, end)
                sen = s[start:end+1]
                if max_len < end-start+1:
                    max_len = end-start+1
                    result = sen 
             
            if s[i-1]!=s[i+1] and s[i-1]!=s[i] and s[i]!=s[i+1]:
                start = i
                end = i
                sen = s[i]
                if max_len < end-start+1:
                    max_len = end-start+1
                    result = sen 

        return result
Runtime: 1940 ms, Memory: 13.8 MB

Other people solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check(l, r):
            while 0 <= l <= r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l + 1:r]
        pals = [check(i, i) for i in range(len(s))] + [check(i, i + 1) for i in range(len(s) - 1) if s[i] == s[i + 1]]


        return sorted(pals, key = len)[-1] if pals else ''
Runtime: 1012 ms, Memory: 14.8 MB

댓글