leetcode 求一个字符串的最长回文子串

最长回文子串问题：给定一个字符串，求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的，那它就是回文串。

给定一个字符串，求它最长的回文子串长度，例如输入字符串'35534321'，它的最长回文子串是'3553'，所以返回 4。

最容易想到的办法是枚举出所有的子串，然后一一判断是否为回文串，返回最长的回文子串长度。不用我说，枚举实现的耗时是我们无法忍受的。那么有没有高效查找回文子串的方法呢？答案当然是肯定的，那就是中心扩展法，选择一个元素作为中心，然后向外发散的寻找以该元素为圆心的最大回文子串。但是又出现了新的问题，回文子串的长度即可能是奇数，也可能好是偶数，对于长度为偶数的回文子串来说是不存在中心元素的。那是否有一种办法能将奇偶长度的子串归为一类，统一使用中心扩展法呢？它就是 manacher 算法，在原字符串中插入特殊字符，例如插入 #后原字符串变成'#3#5#5#3#4#3#2#1#'。现在我们对新字符串使用中心扩展发即可，中心扩展法得到的半径就是子串的长度。

现在实现思路已经明确了，先转化字符串'35534321' ----> '#3#5#5#3#4#3#2#1#'，然后求出以每个元素为中心的最长回文子串的长度。以下给出 python 实现:

#!/usr/bin/python

# -*- coding: utf- -*-

def max_substr(string):

  s_list = [s for s in string]

  string = '#' + '#'.join(s_list) + '#'

  max_length =

  length = len(string)

  for index in range(, length):

    r_length = get_length(string, index)

    if max_length < r_length:

      max_length = r_length

  return max_length

def get_length(string, index):

  # 循环求出index为中心的最长回文字串

  length =

  r_ = len(string)

  for i in range(,index+):

    if index+i < r_ and string[index-i] == string[index+i]:

      length +=

    else:

      break

  return length

if __name__ == "__main__":

  result = max_substr("")

  print (result)

功能已经实现了，经过测试也没有 bug，但是我们静下心来想一想，目前的解法是否还有优化空间呢？根据目前的解法，我们求出了‘35534321‘中每个元素中心的最大回文子串。当遍历到'4'时，我们已经知道目前最长的回文子串的长度 max_length 是 4，这是我们求出了以 4 为中心的最长回文子串长度是 3，它比 max_length 要小，所以我们不更新 max_length。换句话说，我们计算以 4 为中心的最长回文字串长度是做了无用功。这就是我们要优化的地方，既然某个元素的最长的回文子串长度并没有超过 max_length，我们就没有必要计算它的最长回文子串，在遍历一个新的元素时，我们要优先判断以它为中心的回文子串的长度是否能超越 max_length，如果不能超过，就继续遍历下一个元素。以下是优化后的实现：

#!/usr/bin/python

# -*- coding: utf-8 -*-

def max_substr(string):

  s_list = [s for s in string]

  string = '#' + '#'.join(s_list) + '#'

  max_length = 0

  length = len(string)

  for index in range(0, length):

    r_length = get_length2(string, index, max_length)

    if max_length < r_length:

      max_length = r_length

  return max_length

def get_length2(string, index, max_length):

  # 基于已知的最长字串求最长字串

  # 1.中心+最大半径超出字符串范围, return

  r_ = len(string)

  if index + max_length > r_:

    return max_length

  # 2.无法超越最大半径, return

  l_string = string[index - max_length + 1 : index + 1]

  r_string = string[index : index + max_length]

  if l_string != r_string[::-1]:

    return max_length

  # 3.计算新的最大半径

  result = max_length

  for i in range(max_length, r_):

    if index-i >= 0 and index+i < r_ and string[index-i] == string[index+i]:

      result += 1

    else:

      break

  return result - 1

if __name__ == "__main__":

  result = max_substr("")

  print （result）

Leetcode上原题解答如下：

class Solution:

 # 从中心向外扩散

    def helper(self, s, l, r):

        while l >= 0 and r < len(s) and s[l] == s[r]:

            l -= 1; r += 1

        return s[l+1:r]

 # O(n^2)时间复杂度方法

    def longestPalindrome(self, s):

        res = ""

        for i in range(len(s)):

            # 单核回文如 "aba"

            tmp = self.helper(s, i, i)

            if len(tmp) > len(res):

                res = tmp

            # 双核回文如 "abba"

            tmp = self.helper(s, i, i+1)

            if len(tmp) > len(res):

                res = tmp

        return res

转自：https://www.cnblogs.com/dahu-daqing/p/9302681.html

巴特西

leetcode 求一个字符串的最长回文子串

最新文章

热门文章