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"
解题思路1 比较简单易懂,不过对于连续重复的字符串存在耗时操作
解题思路2 是将连续重复字符串看成一个整体了,比如 abbba 下表是01234 相同的不比较了,直接比较相同的左边跟右边
class Solution:
def getTmpAns(self,s,l,r):
size = len(s)
while l>=0 and r<size and s[l] == s[r]:
l = l-1
r = r+1
return s[l+1:r]
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
ans = ""
for i in range(len(s)):
tmpAns = self.getTmpAns(s,i,i)
if len(tmpAns) > len(ans):
ans = tmpAns
tmpAns = self.getTmpAns(s,i,i+1)
if len(tmpAns) > len(ans):
ans = tmpAns
return ans
def _longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
size = len(s)
if size == 1 or size == 0:
return s
if size == 2:
if s[0] == s[1]:
return s
else:
return s[0]
i = 0
maxp = 1
ans = s[0]
while i < size:
j = i+1
while j < size: # let same num as a item like bbb,i是左边起始位置 j是右边起始位置
if s[i] == s[j]:
j += 1
else:
break
k = 0
while i-k-1>=0 and j+k<size:
if s[i-k-1] != s[j+k]:
break
k += 1
if j+k-i+k > maxp:
maxp = j+k-i+k
ans = s[i-k:j+k]
if j+k == size-1:
break
i = j
return ans