(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
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 ''
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 ''
댓글
댓글 쓰기