medium, Array/String
Question:
给定字符串s, 返回最长回文子字符串
For example
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
Solution
抓住回文关于中心对称的特点（中心可能在两个字母之间)
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
start, end = 0, 0
for i in xrange(len(s)):
len1 = self.expandAroundCenter(s, i, i)
len2 = self.expandAroundCenter(s, i, i+1)
maxlen = max(len1,len2)
if maxlen > end-start:
start = i - (maxlen-1)/2
end = i+maxlen/2
return s[start:end+1]
def expandAroundCenter(self, s, left, right):
L, R = left, right
while (L>=0 and R < len(s) and s[L]==s[R]):
L-=1
R+=1
return R-L-1
