leetcode5-- Longest Palindromic Substring

小郑之家~

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"



class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s)<2:
return s

n = len(s)
maxLen = 0
start = 0

for i in range(n-1):
start, maxLen = self.helper(s, i,i,start, maxLen)
start, maxLen = self.helper(s, i, i+1, start, maxLen)
print start, maxLen
return s[start:start+maxLen]

def helper(self, s, left, right, start, maxLen):
"""
s: 是字符串，left是这次要比较的左边的index,right是右边的index, start是最终返回的回文字符串的开始位置，maxLen是最终回文字符串的长度
"""
while(left>=0 and right<len(s) and (s[left]==s[right])):
left -= 1
right += 1

if (maxLen < right-left-1):
maxLen = right-left-1   ## 更新当前的最大长度，因为上面的while结束的时候字符串应该是在[left+1, right-1]所以长度是(right-1-left-1+1).
start = left+1
return start, maxLen



class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s)<2:
return s

n = len(s)
maxLen = 0
start = 0

for i in range(n-1):
self.helper(s, i,i,start, maxLen)
self.helper(s, i, i+1, start, maxLen)

return s[start:start+maxLen]

def helper(self, s, left, right, start, maxLen):
while(left>=0 and right<len(s) and (s[left]==s[right])):
left -= 1
right += 1

if (maxLen < right-left-1):
maxLen = right-left-1
start = left+1



class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s)<2:
return s
n = len(s)
maxLen = 0
start = 0
for i in range(n-1):
start, maxLen = self.helper(s, i, i, start, maxLen)   # 从每一个字符串出发开始找,针对的是bab这种情况
start, maxLen = self.helper(s, i, i+1, start, maxLen)  # 针对的是noon这种情况

return s[start:start+maxLen]

# 因为要不断地更新start, 和maxLen 所以start, maxLen要不断地传入
def helper(self, s, left, right, start, maxLen):
"""
s: 字符串
left,right都是位置
start 是最终要返回的回文字符串的开始的位置
maxLen 是最长的回文字符串的长度

"""
# 注意是从中间往外走，
while left>=0 and right<len(s) and s[left]==s[right]:
left -= 1
right += 1

# 上面结束的时候说明当前的回文截止了，要计长度
# [left+1， right-1]
if maxLen < right-left-1:  # 如果之前的最大值没有现在的大的话，
maxLen = right-left-1 # 更新最大值
start = left + 1    # 也更新初始位置
return start, maxLen