5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd" 输出: "bb"
暴力解法: 列出子串, 求出符合条件的子串存入map, 筛选出最大值存入
func longestPalindrome(s string) string {
if s == "" {
return ""
}
if isPalindrome(s) {
return s
}
pdMap := make(map[string]int)
for i := 0; i < len(s); i++ {
for j:=len(s);j>i+1;j--{
tmp := s[i:j]
//fmt.Println(tmp)
if isPalindrome(tmp) {
pdMap[tmp] = len(tmp)
}
}
}
max := 0
rst := ""
for k,v := range pdMap {
if v > max {
max = v
rst = k
}
}
if rst == "" {
return s[0:1]
}
return rst
}
func isPalindrome(s string) bool {
if len(s) < 1 {
return false
}
if len(s) == 2 && s[0]==s[1]{
return true
}
for i:=0;i<len(s)/2;i++{ // 3/2 = 1 4/2 = 2
if s[i] != s[len(s)-i-1] {
return false
}
}
return true
}
优化1: 因为题目只要求 最长, 所以只需要返回最长的就可以了, 引入map实际上浪费了空间
package main
import "fmt"
//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//
//示例 1：
//
//输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
//示例 2：
//
//输入: "cbbd"
//输出: "bb"
func main() {
s := "abb"
fmt.Println(longestPalindrome(s))
}
func longestPalindrome(s string) string {
if s == "" {
return ""
}
if isPalindrome(s) || len(s) < 2 {
return s
}
max := 0
rst := ""
for i := 0; i < len(s); i++ {
for j:=len(s);j>i+1;j--{
tmp := s[i:j]
//fmt.Println(tmp)
if isPalindrome(tmp) {
if max < len(tmp) {
max = len(tmp)
rst = tmp
}
}
}
}
if rst == "" {
return s[0:1]
}
return rst
}
func isPalindrome(s string) bool {
if len(s) < 1 {
return false
}
if len(s) == 2 && s[0]==s[1]{
return true
}
for i:=0;i<len(s)/2;i++{ // 3/2 = 1 4/2 = 2
if s[i] != s[len(s)-i-1] {
return false
}
}
return true
}
大神解法:
func longestPalindrome(s string) string {
if len(s) < 2 { // 肯定是回文，直接返回
return s
}
// 最长回文的首字符索引，和最长回文的长度
begin, maxLen := 0, 1
// 在 for 循环中
// b 代表回文的**首**字符索引号，
// e 代表回文的**尾**字符索引号，
// i 代表回文`正中间段`首字符的索引号
// 在每一次for循环中
// 先从i开始，利用`正中间段`所有字符相同的特性，让b，e分别指向`正中间段`的首尾
// 再从`正中间段`向两边扩张，让b，e分别指向此`正中间段`为中心的最长回文的首尾
for i := 0; i < len(s); { // 以s[i]为`正中间段`首字符开始寻找最长回文。
if len(s)-i <= maxLen/2 {
// 因为i是回文`正中间段`首字符的索引号
// 假设此时能找到的最长回文的长度为l, 则，l <= (len(s)-i)*2 - 1
// 如果，len(s)-i <= maxLen/2 成立
// 则，l <= maxLen - 1
// 则，l < maxLen
// 所以，无需再找下去了。
break
}
b, e := i, i
for e < len(s)-1 && s[e+1] == s[e] {
e++
// 循环结束后，s[b:e+1]是一串相同的字符串
}
// 下一个回文的`正中间段`的首字符只会是s[e+1]
// 为下一次循环做准备
i = e + 1
for e < len(s)-1 && b > 0 && s[e+1] == s[b-1] {
e++
b--
// 循环结束后，s[b:e+1]是这次能找到的最长回文。
}
newLen := e + 1 - b
// 创新记录的话，就更新记录
if newLen > maxLen {
begin = b
maxLen = newLen
}
}
return s[begin : begin+maxLen]
}
这里还有一些算法, 由leetCode官方提供:
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/