如何高效判断字符串是否为回文,或仅需删除一个字符即可构成回文

21次阅读

如何高效判断字符串是否为回文,或仅需删除一个字符即可构成回文

给定一个 ASCII 字符串(保证本身是回文,或删去**恰好一个字符**后可变为回文),需在 o(n) 时间内返回:若已是回文则返回 -1;否则返回**唯一可删除字符的索引**。避免构造新字符串,杜绝 o(n²) 低效遍历。

传统思路(如原代码中 findIdx 调用 RemoveChar + Palindrome)存在严重性能瓶颈:每尝试删除一个位置,都需复制子串并完整校验回文,时间复杂度达 O(n²),对长字符串极不友好。

更优解法基于「双指针+单次扫描」思想:从两端向中间匹配,首次遇到不等时(设位置为 i 和 n-1-i),问题必源于删除左端 i 或右端 n-1-i 处的字符。此时只需分别验证两个候选子串是否为回文:

  • 候选1:跳过左字符 → 检查 s[i+1 : n-i] 是否回文
  • 候选2:跳过右字符 → 检查 s[i : n-i-1] 是否回文

但注意:原答案提供的优化版本进一步省去了显式子串切片和完整回文校验——它利用已知“至多一个差异”的前提,在发现首处不匹配后,直接在局部范围内用嵌套循环快速判定应删左还是右。该逻辑虽精巧,但可读性较低且边界易错。

推荐采用清晰、稳健、真正 O(n) 的双指针方案:

func findIdx(s String) int {     n := len(s)     left, right := 0, n-1      for left < right {         if s[left] != s[right] {             // 尝试跳过 left:检查 [left+1, right] 是否回文             if isPalindrome(s, left+1, right) {                 return left             }             // 尝试跳过 right:检查 [left, right-1] 是否回文             if isPalindrome(s, left, right-1) {                 return right             }             return -2 // 理论上不会到达(题目保证至多删一字符)         }         left++         right--     }     return -1 // 已是回文 }  // 辅助函数:检查 s[lo:hi+1] 是否为回文(闭区间) func isPalindrome(s string, lo, hi int) bool {     for lo < hi {         if s[lo] != s[hi] {             return false         }         lo++         hi--     }     return true }

关键优势

  • 时间复杂度 O(n):最多遍历字符串常数次(主循环 + 最多两次子区间检查);
  • 空间复杂度 O(1):无字符串拼接,不分配额外内存;
  • 鲁棒性强:边界清晰,逻辑直觉明确,易于测试与维护。

⚠️ 注意事项

  • 切勿使用 s[0:i] + s[i+1:] 类型拼接——go 中字符串不可变,每次拼接均触发内存分配与拷贝,对长字符串代价高昂;
  • isPalindrome 应设计为接受索引范围的辅助函数,避免创建子串(Go 的切片操作虽不拷贝底层数组,但 string 类型的切片仍需构造新字符串头,而本方案中 s[lo:hi+1] 是安全的,因底层字节数组共享,但为极致效率,也可直接传入原串及坐标);
  • 题目约束(“必可删一字符成回文”)确保解唯一,无需处理多解或无解场景,但代码中保留 -2 作为防御性兜底。

综上,摒弃暴力枚举,转而利用回文结构的对称性与题目强约束,用两次局部双指针验证替代全局重检,即可在保持代码简洁的同时实现最优性能。

text=ZqhQzanResources