回文字串---开始刷题1
首先明确“回文”串 是什么:是一个字符串在正读和反读时完全相同。也就是,把这个字符串从中间对折,左右两边的字符能够完全重合。
数学定义:对于一个长度为n的字符串S,如果对于所有的 0<=i<n,都满足s[i] == s[n-1-i],那么该字符串就是回文串。
一些示例:
| 类型 | 示例 | 说明 |
|---|---|---|
| 单词/字母 | madam,racecar,level | 忽略大小写后正反读一致 |
| 数字串 | 12321,1221,666 | 数字序列对称 |
| 中文 | 上海自来水来自海上 | 汉字序列对称 |
| 特殊 | a,aa,""(空串) | 单个字符和空串也被视为回文 |
回文串通常考察:
1、双指针技巧:使用头尾两个指针向中间逼近来判断是否为回文(时间复杂度O(n),空间复杂度O(1))。
2、动态规划:解决“最长回文子串”、“回文子串计数”等问题。
3、字符串哈希/Manacher算法:用于在O(n)时间内高效查找所有回文子串。
4、递归与分治:判断回文本身具有天然的递归结构。
力扣题---解决寻找最长回文子串问题;
第一步:先用人脑模拟一下:(每个子串都有一个中心,可以使用中心扩展法)
对于“babad”:
以b(索引0)为中心向两边扩-》只有b自己,长度1;
以a(索引1)为中心向两边扩-》b-a-b ;长度3;
以b(索引2)为中心向两边扩-》a-b-a;长度3;
以a(索引3)为中心向两边扩-》b-a-d;不是回文串,只有a自己
以d(索引4)为中心向两边扩-》只有d
关键洞察:每个回文串一定有一个“中心”。我们只需要枚举每一个可能的中心,然后向两边扩展,记录最长的即可。
但是需要注意:回文可能是奇数长度(aba,中心是一个字符),也可能是偶数长度(如bb,中心是两个字符之间的缝隙)。所以每个位置要尝试两种中心。
先判断的是否相等,然后再进行的-1 ,两边都进行了-1 ;因此都是多走了一步,需要用right-left-1;得到的就是长度;
使用这种扩展中心法来先写代码:
正确的验证可通过的代码:
func longestPalindrome(s string) string { if len(s)==0{ return "" } start , maxLen := 0,1 //记录最长回文的起始位置和长度 //expandAroundCenter 从给定的左右中心向两边扩展,返回回文长度 expandAroundCenter := func(left,right int)int { for left >= 0 && right < len(s)&&s[left]==s[right] { left-- right++ } //循环结束时 left 和 right 各自走了一步 return right - left -1 } for i := 0 ; i <len(s) ; i++ { // 情况1:奇数长度回文,中心是s[i] oddLen := expandAroundCenter(i,i) //情况2:偶数长度回文,中心是s[i] 和 s[i+1]之间 evenLen := expandAroundCenter(i,i+1) //取两者较大值 curLen := oddLen if evenLen > curLen { curLen = evenLen } // 更新全局最优 if curLen >maxLen{ maxLen = curLen start = i -(maxLen-1)/2 //推导,中心i向左偏移(len-1)/2 } } return s[start:start+maxLen] }正确运行的结果:
这部分代码是我根据梳理完思路后自己又写了一遍;有一些错误的点,
func lenlongStr (s string )string{ if len(s)==0{ return "" } // 计算回文串长度方案 exelenStr := func (left,right) int { for left >0 && right < len(s) && s[left]==s[right] { left-- rigth++ } ruturn right -left -1 // 两个都有多走一步,因为先进行的相等判断,直接向下各走一步 } start , maxlen := 0,1 // 用来获取最后要输出的串,以及获取最大的长度的回文串 for i := 0 ; i< len(s) ;i++{ //回文串是奇数,中心为i oddlen := exelenStr(i,i) // 回文串是偶数,中心为i 和i+1 explen := exelenStr(i,i+1) //设置一个变量,获取两种中心串的最大值; curlen := oddlen if explen > curlen{ curlen := explen } //再去实际的赋值到 maxlen 这个最大值 上 if curlen > maxlen{ maxlen := curlen start := i - (maxlen-1)/2 //起始值距离 i ,用i这个中心减去长度的一半 } } ruturn s[start,start+maxlen] }在这里纠正相关的错误点;直接让ai检查的
你这次自己默写的代码非常有价值!虽然报错很多,但核心逻辑(中心扩展法)你已经完全掌握了,这说明你的思路是正确的。
现在的问题纯粹是Go 语言语法细节和变量作用域的坑。对于新手来说,这些都是必经之路。我帮你把问题逐一拆解:
🔍 错误清单与修复
1. 函数参数必须声明类型
- 你的代码:
func (left,right) int { - 问题:Go 是强类型语言,闭包函数的参数也必须写明类型。
- 修复:
func(left, right int) int {
2. 边界条件少了一个等号(⚠️ 逻辑 Bug)
- 你的代码:
for left > 0 && ... - 问题:如果回文串刚好从索引
0开始(比如"aba"),left减到0时,left > 0为假,循环提前退出,导致漏掉首字符。 - 修复:必须是
left >= 0。
3. 拼写错误三连
rigth++→ 应为right++ruturn→ 应为return(出现了两次)lenlongStr→ 题目要求的函数名是longestPalindrome(LeetCode 会因找不到入口函数而报错)
4. 变量作用域陷阱(⚠️ 最隐蔽的 Bug)
这是新手在 Go 中最容易踩的坑:
// ❌ 你的代码 if explen > curlen { curlen := explen // 这里用 := 创建了一个新的局部变量! } // 出了 if 块,这个新 curlen 就消失了 // 外面的 curlen 依然是 oddlen! if curlen > maxlen { maxlen := curlen // 同样的问题!创建了新的局部 maxlen start := i - (maxlen-1)/2 // 创建了新的局部 start } // 外层的 start 和 maxlen 从未被更新!- 规则:
:=是短变量声明,会在当前块级作用域创建新变量。如果你只是想赋值给外层已有的变量,必须用=。 - 修复:
if explen > curlen { curlen = explen // ✅ 用 = 赋值 } if curlen > maxlen { maxlen = curlen // ✅ 用 = 赋值 start = i - (maxlen-1)/2 // ✅ 用 = 赋值 }✅ 修正后的完整代码
func longestPalindrome(s string) string { if len(s) == 0 { return "" } // 1. 参数加类型;2. left >= 0;3. right 拼写正确 exelenStr := func(left, right int) int { for left >= 0 && right < len(s) && s[left] == s[right] { left-- right++ } return right - left - 1 // ruturn → return } start, maxlen := 0, 1 for i := 0; i < len(s); i++ { oddlen := exelenStr(i, i) explen := exelenStr(i, i+1) curlen := oddlen if explen > curlen { curlen = explen // ✅ := 改为 = } if curlen > maxlen { maxlen = curlen // ✅ := 改为 = start = i - (maxlen-1)/2 // ✅ := 改为 = } } return s[start : start+maxlen] // ruturn → return,切片语法用冒号 }💡 给你的学习建议
- 关于
:=vs=:这是 Go 新手第一道坎。记住口诀:第一次出现用:=,后续修改用=。在if/for块内修改外层变量时,永远只用=。 - 不要气馁:你第一次独立默写就能把中心扩展法的框架、奇偶双中心、长度计算公式全部写对,这比很多刷了几十题的人还强。剩下的只是语法熟练度问题。
- 下一步练习:把修正后的代码再删掉,凭记忆重写一遍。这次重点关注
>=、=和拼写。当你能一次性无错写出来时,这道题就真正属于你了。
你已经走在正确的路上了,继续加油!💪
加油加油!今天就先到这里了!