目录

题目描述

输入/输出示例

解决方案

暴力法

中心扩散法

Manacher算法

代码

暴力法

中心扩散法

Manacher算法

代码走读

暴力法

中心扩散法

Manacher算法

传送门

题目描述

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

输入/输出示例

解决方案

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

暴力法

很明显，暴力法将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。因为要循环遍历每一个元素作为子串的开头，对每一个元素要寻找结尾，且对每一次可能的结尾要判断子串是否回文，因此暴力法的时间复杂度为：，空间复杂度为。

中心扩散法

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

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

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

复杂度分析：时间复杂度为。空间复杂度为 。

Manacher算法

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

代码

暴力法

package main

import "fmt"

func longestPalindrome(s string) string {
	if len(s) < 2 {
		return s
	}

	maxSubPalindrome := s[:1]
	for i := 0; i < len(s)-1; i++ {
		for j := i + 1; j < len(s); j++ {
			if j-i+1 > len(maxSubPalindrome) && isPalindrome(s[i:j+1]) {
				maxSubPalindrome = s[i : j+1]
			}
		}
	}

	return maxSubPalindrome
}

func isPalindrome(subStr string) bool {
	for i := 0; i < len(subStr)/2; i++ {
		if subStr[len(subStr)-i-1] != subStr[i] {
			return false
		}
	}

	return true
}

中心扩散法

package main

import "fmt"

func longestPalindrome(s string) string {
	if len(s) < 1 {
		return s
	}

	maxSubPalindrome := s[:1]
	for i := 0; i < len(s); i++ {
		evenPalindrome := GetPalindrome(s, i, i)
		oddPalindrome := GetPalindrome(s, i, i+1)
		maxSubPalindrome = MaxString(
			evenPalindrome,
			oddPalindrome,
			maxSubPalindrome,
		)
	}
	return maxSubPalindrome
}

func GetPalindrome(s string, left, right int) string {
	for {
		if !(left >= 0 && right < len(s) && s[left] == s[right]) {
			break
		}

		left--
		right++
	}

	return s[left+1 : right]
}

func MaxString(strList ...string) string {
	max := ""
	for _, str := range strList {
		if len(str) > len(max) {
			max = str
		}
	}
	return max
}

Manacher算法

package main

import (
	"fmt"
	"strings"
)

func longestPalindrome(s string) string {
	if len(s) < 2 {
		return s
	}

	return Manacher(s)
}

func Manacher(s string) string {
	manacherStr := "#" + strings.Join(strings.Split(s, ""), "#") + "#"
	maxLength := 0
	start := 0
	for i := 0; i < len(manacherStr); i++ {
		left := i - 1
		right := i + 1
		step := 0

		for {
			if !(left >= 0 && right < len(manacherStr) &&
				manacherStr[left] == manacherStr[right]) {
				break
			}
			left--
			right++
			step++
		}

		if step > maxLength {
			maxLength = step
			start = (i - maxLength) / 2
		}
	}
	return s[start : start+maxLength]
}

代码走读

暴力法

package main

import "fmt"

func longestPalindrome(s string) string {
   // 空字符串或长度为1的字符串肯定是回文字符串，直接返回即可
   if len(s) < 2 {
      return s
   }

   // 初始化最长回文子串：取首字符构成的子串作为最长回文子串
   maxSubPalindrome := s[:1]

   // 设置两个游标变量，i从头到尾-1依次遍历，将每个字符作为子串的首字符下标，
   // j作为子串的尾字符下标，依次检查s[i:j+1]是否为最长回文字符串
   for i := 0; i < len(s)-1; i++ {
      for j := i + 1; j < len(s); j++ {
         if j-i+1 > len(maxSubPalindrome) && isPalindrome(s[i:j+1]) {
            maxSubPalindrome = s[i : j+1]
         }
      }
   }

   return maxSubPalindrome
}

// 判断某个子串是否是回文字符串
func isPalindrome(subStr string) bool {
   for i := 0; i < len(subStr)/2; i++ {
      if subStr[len(subStr)-i-1] != subStr[i] {
         return false
      }
   }

   return true
}

// 自测用例
func main() {
   fmt.Println(longestPalindrome("a"))
}

中心扩散法

package main

import "fmt"

func longestPalindrome(s string) string {
   if len(s) < 1 {
      return s
   }

   // 分别以奇数子串和偶数子串为中心向两边扩散，找出最长子串
   maxSubPalindrome := s[:1]
   for i := 0; i < len(s); i++ {
      evenPalindrome := GetPalindrome(s, i, i)
      oddPalindrome := GetPalindrome(s, i, i+1)
      maxSubPalindrome = MaxString(
         evenPalindrome,
         oddPalindrome,
         maxSubPalindrome,
      )
   }
   return maxSubPalindrome
}

// 以s[left:right+1]向两边扩散，找出最长回文子串
func GetPalindrome(s string, left, right int) string {
   for {
      if !(left >= 0 && right < len(s) && s[left] == s[right]) {
         break
      }

      left--
      right++
   }

   return s[left+1 : right]
}

// 找出最长字符串
func MaxString(strList ...string) string {
   max := ""
   for _, str := range strList {
      if len(str) > len(max) {
         max = str
      }
   }
   return max
}

// 自测用例
func main() {
   fmt.Println(longestPalindrome("babaddab"))
}

Manacher算法

package main

import (
   "fmt"
   "strings"
)

func longestPalindrome(s string) string {
   if len(s) < 2 {
      return s
   }

   return Manacher(s)
}

func Manacher(s string) string {
   // 将一个可能是偶数长/奇数长的字符串，首尾以及每个字符之间添加 "#"，确保添加后长度变为奇数的字符串
   manacherStr := "#" + strings.Join(strings.Split(s, ""), "#") + "#"

   // 记录最长回文子串的长度
   maxLength := 0

   // 记录最长回文子串的首字符对应原字符串s中首字符的索引位置
   start := 0
   for i := 0; i < len(manacherStr); i++ {
      left := i - 1
      right := i + 1
      // 扩散次数。因为manacher字符串的构造，此时扩散次数等于最长回文串的长度
      step := 0

      for {
         if !(left >= 0 && right < len(manacherStr) &&
            manacherStr[left] == manacherStr[right]) {
            break
         }
         left--
         right++
         step++
      }

      // 计算起始位置start
      if step > maxLength {
         maxLength = step
         start = (i - maxLength) / 2
      }
   }
   return s[start : start+maxLength]
}

func main() {
   fmt.Println(longestPalindrome("cababa"))
}

传送门

LeetCode试题链接

strings.Split()函数