5. Longest Palindromic Substring

给定一个字符串s，找到它最长的palindromic substring，可以假设这个字符串的长度不大于1000.
note:palindromic substring 回文字符串

• Example 1

输入：babad
输出：bab（aba也正确）

• Example 2

输入：cbbd
输出：bb

思路

对于一个回文字符串，它从前往后读和从后往前读结果是一样的。单个字符是回文，对于一个字符串来说，它是回文的当且仅当：它去掉两边的字符后是回文的，并且两边的两个字符相同。也就是：

image.png

因此，我们可以从每个单个字符开始，作为中心，寻找最大的回文字符串，也可以从两个字符开始，作为中心，向两边寻找最大回文字符串。
这次试用python实现。

class Solution:
  def longestPalindrome(self, s):
    end = 0
    start = 0
    if len(s) == 0:
      return ''
    
    for i in range(len(s)):
      l1 = expand(s, i, i)
      l2 = expand(s, i, i + 1)
      g = max(l1, l2)
      if g > (end - start):
        start = i - int((g - 1) / 2)
        end = i + int(g / 2)
    
    return s[start:end + 1]


def expand(s, l, r):
  while (l >= 0 and r < len(s) and s[l] == s[r]):
    l -= 1
    r += 1
  return r - l - 1

if __name__ == '__main__':
  s = Solution()
  print(s.longestPalindrome('babad'))

  print(s.longestPalindrome('cbbd'))