5. 最长回文子串

题目描述

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

示例

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

示例 2：
输入: "cbbd"
输出: "bb"

解法

func longestPalindrome(s string) string {
	var (
		subStr        = ""
		lenS          int
		index         int
		subK          int
		maxLeftIndex  int
		maxRightIndex int
	)
	lenS = 2*len(s) - 1
	for index < lenS {
		subK = 0
		for {
			leftIndex, rightIndex := index-subK, index+subK
			if leftIndex%2 != 0 {
				leftIndex--
			}
			if rightIndex%2 != 0 {
				rightIndex++
			}
			if leftIndex < 0 || rightIndex >= lenS {
				break
			}
			if s[leftIndex/2] == s[rightIndex/2] {
				if maxRightIndex-maxLeftIndex < rightIndex/2-leftIndex/2 {
					maxLeftIndex, maxRightIndex = leftIndex/2, rightIndex/2
				}
				subK++
			} else {
				break
			}
		}
		index++
	}
	if maxRightIndex < len(s) {
		subStr = s[maxLeftIndex:maxRightIndex+1]
	}
	return subStr
}

本地测试

package main

import "fmt"

func main() {
	s := "babad"
	fmt.Println(longestPalindrome(s))
	s = "cbbd"
	fmt.Println(longestPalindrome(s))
	s = "abcd"
	fmt.Println(longestPalindrome(s))
	s = "cbbb"
	fmt.Println(longestPalindrome(s))
	s = "bbbc"
	fmt.Println(longestPalindrome(s))
	s = "ababa"
	fmt.Println(longestPalindrome(s))
	s = "bbbb"
	fmt.Println(longestPalindrome(s))
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring