jsp-basic

最长回文子串

题目地址：最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

思路

回文串特点：关于中心字符对称（长度为奇数）或者关于中心线对称（长度为偶数）

中心扩散法：遍历每一个字符，同时向左右扩散，判断扩散到的两个字符是否相同，如果相同，继续扩散；如果不同，停止

代码

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        max_l = 0
        res = ""
        for i in range(0, len(s)):
            #以s[i] 为中心向左右扩散
            left, right = i, i
            while(left >= 0 and right < len(s) and s[left] == s[right]):
                if max_l < right - left + 1:
                    max_l = right - left + 1
                    res = s[left:right + 1]
                left -= 1
                right += 1

            #以s[i],s[i+1]为中心向左右扩散
            left, right = i, i + 1
            while(left >= 0 and right < len(s) and s[left] == s[right]):
                if max_l < right - left + 1:
                    max_l = right - left + 1
                    res = s[left:right + 1]
                left -= 1
                right += 1
        return res

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 changzeyan@foxmail.com