【Leetcode】5. 最长回文子串 ＜字符串、暴力＞

题目描述: 5. 最长回文子串

考察算法 : 回文串、字符串、暴力、模拟

闲话短说 : 注意本题的数据范围为[1,1000]，所以只要保证算法时间复杂度在O(N^2)即可。回文串分两种,12321 or 123321,一种长度为奇数,一种长度为偶数。要寻找字符串中的最长回文子串,采用中心扩展的方式,以某个字符为中心，向两边扩展，因为我们不确定与这个字符相匹配的是奇数回文串还是偶数回文串，所以需要分开考虑。

AC Code:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        new_s = ''
        res = 0
        for i in range(0,length):
            # 1、奇数回文串扩散
            step = 0
            while i - step >= 0 and i + step < length:
                if s[i-step] == s[i + step]:
                    if step * 2 + 1 > res:
                        res = step * 2 + 1
                        new_s = s[i - step:i + step + 1]
                else :
                    break
                step += 1
            # 2、偶数回文串扩散
            l,r = i,i + 1
            while l >= 0 and r < length:
                if s[l] == s[r] :
                    if r - l + 1 > res:
                        res = r - l + 1
                        new_s = s[l:r + 1]
                else :
                    break
                l -= 1
                r += 1
        return new_s