题目描述

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

输入/输出示例

输入	babad
输出	bab
解释	输入的字符串中最长的回文子串为bab。注意aba也是一个正确答案。

解决方案

解决的方法大概分为以下三种：

暴力法

很明显，暴力法将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。在利用Python分片的优势下，时间复杂度为 $O(n^{2})$ 。空间复杂度为 $O(1)$ 。

需要注意的是，在Python语言优势下（分片的使用）暴力法的时间复杂度并不高，但是在不支持分片功能的语言里（例如Go，虽然支持切片，但是跟Python分片还是有一定区别的），暴力法的时间复杂度会达到惊人的 $O(n^{3})$ 。

中心扩散法

暴力法虽然逻辑简单清晰，但是会带来太多的重复计算。我们通过观察发现，单个字符肯定是回文字符串。如果单个字符的左右两边拥有相邻的字符，且左右两边相邻的字符相等，那么这三个字符所组成的字符串一定就是回文字符串。按照这个逻辑依此类推，就可以找到中心字符串不断向两边扩散的最长回文串。我们通过循环可以将每个字符视为一个“中心字符”，对每一个中心字符向两边扩散，找到最长的记录，就是我们要的结果。

但是会有一种情况在上面描述的逻辑中没有考虑到：如果是长度为偶数的回文字符串，例如abba，使用上面以单个字符作为中心向两边扩散的逻辑无法找到最终结果“abba”，而是会得到一个错误的结果“a”。因此我们还要考虑对长度为偶数字符串的场景：我们选取两个相邻的字符串作为“中心”。如果这两个字符相等，那么就依次向两边扩散，如果每次扩散的最外层左右两边字符相等，那么这些字符所构成的字符串就是我们要找的回文字符串。依次遍历完全部字符串后找到的长度最大的回文子串就是我们想要的结果。

综上所述，要找到一个字符串中的最大回文子串，我们不仅要以单个字符向两边扩散求解，还要对两个相同且相邻的字符向两边扩散求解。最终对两个方法求解的结果进行比较，找到长度最大的字符串，就是我们想要的结果，即最长回文子串。

复杂度分析：时间复杂度为 $O(n^{2})$ 。空间复杂度为 $O(1)$ 。

Manacher算法

Manacher算法是对中心扩散法的一种优化。因为中心扩散法要对子串长度的奇偶分别进行计算，消耗了大量的时间。如果我们对奇偶转换成统一的模式进行计算，就会减少大量的时间消耗。因此Manacher算法的核心是，将原字符串（无论奇偶）构造成一个长度完全是奇数的字符串：构造后无论是长度，还是内部字符和字符之间的距离都变成了奇数。这种构造新字符串的方式就是将原字符串的首尾和每个字符之间都插入一个特殊的标志字符。例如假设原字符串为“abba”，通过插入特殊字符的方式将字符串构造为“#a#b#b#a”。需要注意的是，该特殊字符不能存在于原始字符串中。我们对构造后的字符串利用中心扩散法的思想求出最长回文子串。

代码

暴力法

class Solution:    def longestPalindrome(self, s: str) -> str:        if s == s[::-1]:            return s        max_sub_palindrome_string = s[0]        for i in range(len(s)-1):            for j in range(i+1, len(s)):                if j - i + 1 > len(max_sub_palindrome_string) and \                        s[i:j+1] == s[i:j+1][::-1]:                    max_sub_palindrome_string = s[i:j+1]        return max_sub_palindrome_string

中心扩散法

class Solution:    def longestPalindrome(self, s: str) -> str:        if s == s[::-1]:            return s        max_sub_palindrome_string = s[0]        for index in range(len(s)):            palindrome_odd = Solution.get_palindrome(index, index, s)            palindrome_even = Solution.get_palindrome(index, index+1, s)            max_sub_palindrome_string = max(                palindrome_odd,                palindrome_even,                max_sub_palindrome_string,                key=len,            )        return max_sub_palindrome_string    @staticmethod    def get_palindrome(left, right, s) -> str:        while left >= 0 and right < len(s) and s[left] == s[right]:            left -= 1            right += 1        return s[left+1:right]

Manacher算法

class Solution:    def longestPalindrome(self, s: str) -> str:        return self.manacher(s)    @staticmethod    def manacher(s: str) -> str:        if len(s) < 2:            return s        # 将一个可能是偶数长/奇数长的字符串，首位以及每个字符间添加#        manacher_length = len(s)*2+1        manacher_str = "#".join(s).center(manacher_length, "#")        max_palindrome = ""        for i in range(manacher_length):            left = i - 1            right = i + 1            while left >= 0 and right < manacher_length and \                    manacher_str[left] == manacher_str[right]:                left -= 1                right += 1            if right - left + 1 > len(max_palindrome):                max_palindrome = manacher_str[left+1:right]        return max_palindrome.replace("#", "")

代码走读

暴力法

class Solution:    def longestPalindrome(self, s: str) -> str:        # 如果s本身回文，或s为空字符，则返回s        if s == s[::-1]:            return s        # 因为单字符本身回文，因此初始化最长子回文串为首字符        max_sub_palindrome_string = s[0]        # 设置两个游标变量，i从头到尾-1依次遍历，将每个字符作为子串的首字符        # j 作为子串的尾字符, 依次检查s[i:j+1]是否为最长回文串        for i in range(len(s)-1):            for j in range(i+1, len(s)):                if j - i + 1 > len(max_sub_palindrome_string) and \                        s[i:j+1] == s[i:j+1][::-1]:                    max_sub_palindrome_string = s[i:j+1]        return max_sub_palindrome_string# 自测用例if __name__ == '__main__':    s = Solution()    result = s.longestPalindrome("hada")    print(result)

中心扩散法

class Solution:    def longestPalindrome(self, s: str) -> str:        if s == s[::-1]:            return s        max_sub_palindrome_string = s[0]        for index in range(len(s)):            # 分别以奇数子串和偶数子串为中心向两边扩散，找出最长子串            palindrome_odd = Solution.get_palindrome(index, index, s)            palindrome_even = Solution.get_palindrome(index, index+1, s)            max_sub_palindrome_string = max(                palindrome_odd,                palindrome_even,                max_sub_palindrome_string,                key=len,            )        return max_sub_palindrome_string    # 以s[left:right+1]为中心向两边扩散，寻找最长回文子串    @staticmethod    def get_palindrome(left, right, s) -> str:        while left >= 0 and right < len(s) and s[left] == s[right]:            left -= 1            right += 1        return s[left+1:right]# 自测用例if __name__ == '__main__':     s = Solution()     result = s.longestPalindrome("babad")     print(result)

Manacher算法

class Solution:    def longestPalindrome(self, s: str) -> str:        return self.manacher(s)    @staticmethod    def manacher(s: str) -> str:        # 如果s是单字符的字符串，那么直接返回        if len(s) < 2:            return s            # 将一个可能是偶数长/奇数长的字符串，首位以及每个字符间添加#，确保添加后变成了长度为奇数的字符串        manacher_length = len(s)*2+1        manacher_str = "#".join(s).center(manacher_length, "#")        # 记录最长子回文串        max_palindrome = ""        for i in range(manacher_length):            left = i - 1            right = i + 1            while left >= 0 and right < manacher_length and \                    manacher_str[left] == manacher_str[right]:                left -= 1                right += 1            # 将左右指针回退一位，得到本次遍历的回文串长度：(right - 1) - (left + 1) - 1 = right - left - 1            if right - left - 1 > len(max_palindrome):                max_palindrome = manacher_str[left+1:right]         # 由于max_palindrom是包含特殊字符#的回文子串，因此需要将#字符删除后返回        return max_palindrome.replace("#", "")# 自测用例if __name__ == '__main__':    s = Solution()    result = s.longestPalindrome("babad")    print(result)

传送门

转载地址：http://hdsoi.baihongyu.com/

你可能感兴趣的文章

程序员身上有异味，同事为什么都不会直接告诉他？