题目描述

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"

# -*- coding: utf-8 -*-
# @Time         : 2019-10-11 10:34
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : longestPalindromicSubstring.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    """
    要查找最长的回文子串，这里可以把我们的思路换一下。
    原本我们判断一个字符串是不是回文的时候，是从字符串的两端开始往中间比较，
    而我们现在要找的是最长的回文子串，那么如果我们从中间开始往两段比较，直到待比较的两个字符不相等。

    通过不断的将中心字符移动，这样我们就可以找到最长的回文子串。
    需要注意的是，在我们判断一个字符串的是不是回文的时候需要处理字符串个数的奇偶性
    同理，我们在移动中心字符的时候，也要处理奇数字符长度的回文子串和偶数字符长度的回文子串。
    """
    def longestPalindrome(self, s):
        def helper(left, right):
            """
            判断给定一个字符串的起止点，最多能将其延长到多长。
            :param left: 起点
            :param right: 终点
            :return: 以left, right为起止点能延长到的最长回文字符串
            """
            # 只要下标不越界并且两端相等，就往外延伸
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # 当不能再延伸的时候，返回当前能得到的最长回文字符串
            return s[left + 1: right]

        ans = ''
        for i in range(len(s)):
            # 对于每一个中心，需要判断奇数长度的回文子串和偶数长度的回文子串
            odd = helper(i, i)
            if len(odd) > len(ans):
                ans = odd
            even = helper(i, i + 1)
            if len(even) > len(ans):
                ans = even
        return ans

def main():
    solution = Solution()
    s = "babad"
    print(solution.longestPalindrome(s))

if __name__ == '__main__':
    main()