重庆市建设工程网官网_深圳免费网站建设服务_万网建站_室内设计网站

给你一个字符串 s，找到 s 中最长的回文子串

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

看似困难，实则一点也不简单

方法：中心扩展法（Expand Around Center）

思路：
回文字符串具有对称性，因此我们可以以每个字符为中心，向两边扩展，找到最长的回文子串。需要注意的是，回文可能是奇数长度或偶数长度。

步骤：

1. 遍历字符串中的每个字符。
2. 对于每个字符，分别以奇数长度和偶数长度为中心进行扩展。
3. 记录最长的回文子串。

func longestPalindrome(s string) string {if len(s) == 0 {return ""}var maxLen int var start int for i:=0;i<len(s);i++{//奇数长度的回文l,r := i,i for l>=0 && r<len(s) && s[l] == s[r] {if r-l+1>maxLen {maxLen = r-l+1start = l }l--r++}// 偶数长度的回文l,r = i,i+1for l>= 0 && r < len(s) && s[l] == s[r] {if r-l+1 > maxLen {maxLen = r-l+1start =l }l--r++}}return s[start:start+maxLen]
}

解释：

• 首先检查字符串是否为空，如果是则返回空字符串。
• 初始化 maxLen 为最大回文长度，start 为最长回文子串的起始位置。
• 遍历字符串中的每个字符 i。
  • 对于奇数长度的回文，以 i 为中心向两边扩展。
  • 对于偶数长度的回文，以 i 和 i+1 为中心向两边扩展。
• 在每次扩展中，如果当前回文长度大于 maxLen，则更新 maxLen 和 start。
• 最后返回最长回文子串。