leetcode 5：最長回文子串

題目描述

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:
    """
    要查找最長的回文子串，這里可以把我們的思路換一下。
    原本我們判斷一個(gè)字符串是不是回文的時(shí)候，是從字符串的兩端開始往中間比較，
    而我們現(xiàn)在要找的是最長的回文子串，那么如果我們從中間開始往兩段比較，直到待比較的兩個(gè)字符不相等。

    通過不斷的將中心字符移動(dòng)，這樣我們就可以找到最長的回文子串。
    需要注意的是，在我們判斷一個(gè)字符串的是不是回文的時(shí)候需要處理字符串個(gè)數(shù)的奇偶性
    同理，我們?cè)谝苿?dòng)中心字符的時(shí)候，也要處理奇數(shù)字符長度的回文子串和偶數(shù)字符長度的回文子串。
    """
    def longestPalindrome(self, s):
        def helper(left, right):
            """
            判斷給定一個(gè)字符串的起止點(diǎn)，最多能將其延長到多長。
            :param left: 起點(diǎn)
            :param right: 終點(diǎn)
            :return: 以left, right為起止點(diǎn)能延長到的最長回文字符串
            """
            # 只要下標(biāo)不越界并且兩端相等，就往外延伸
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # 當(dāng)不能再延伸的時(shí)候，返回當(dāng)前能得到的最長回文字符串
            return s[left + 1: right]

        ans = ''
        for i in range(len(s)):
            # 對(duì)于每一個(gè)中心，需要判斷奇數(shù)長度的回文子串和偶數(shù)長度的回文子串
            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()