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 code:
class Solution(object):
def longestPalindrome(self, s):
if len(s) < 2:
return s
longest = s[0]
for i in range(len(s) - 1):
if i > 0 and s[i-1] == s[i+1]:
pal = self.palindrome_around(s, i-1, i+1)
if len(pal) > len(longest):
longest = pal
if s[i] == s[i+1]:
pal = self.palindrome_around(s, i, i+1)
if len(pal) > len(longest):
longest = pal
return longest
def palindrome_around(self, s, i, j):
prev_idx = i - 1
next_idx = j + 1
pal = s[i:j+1]
is_valid = True
while prev_idx >= 0 and next_idx < len(s) and is_valid:
if s[prev_idx] == s[next_idx]:
pal = s[prev_idx:next_idx+1]
prev_idx -= 1
next_idx += 1
else:
is_valid = False
return pal
def longestPalindrome1(self, s):
"""
:type s: str
:rtype: str
"""
self.record=[[-1]*len(s) for k in range(len(s))]
result=self.Find_Palindrome(s,0,len(s)-1)
#print(self.record)
return result
def Find_Palindrome(self,s,i,j):
#print('checked0 i %d,j %d'%(i,j))
#print(self.record)
if i>j:
return ""
if j==i:
return s[i]
if self.record[i][j]!=-1:
#print('accessed i %d,j %d'%(i,j))
return self.record[i][j]
#print('checked i %d,j %d'%(i,j))
result1=""
tmp_str=s[i:j+1]
if tmp_str==tmp_str[::-1]:
result1=tmp_str
#print(tmp_str)
#print('SET i %d,j %d'%(i,j))
self.record[i][j]=result1
return result1
result2=self.Find_Palindrome(s,i+1,j)
result3=self.Find_Palindrome(s,i,j-1)
length2=len(result2)
length3=len(result3)
if length2 >length3:
self.record[i][j]=result2
else:
self.record[i][j]=result3
#print('SET i %d,j %d'%(i,j))
return self.record[i][j]
Solution: https://leetcode.com/problems/longest-palindromic-substring/