大家好今日打卡分享一道经典字符串中等难度算法题验证回文串II。本题是回文类题目的进阶版本也是大厂笔试高频考点核心考察双指针贪心思想的应用。题目题意给定一个字符串 s 你最多可以从中删除一个字符判断字符串是否可以成为回文字符串。如果可以返回 true 否则返回 false 。- 示例1输入 aba 无需删除字符本身就是回文串返回 true- 示例2输入 abca 删除字符 c 后变为 aba 是回文串返回 true- 示例3输入 abc 删除任意一个字符都无法形成回文串返回 false核心解题思路双指针贪心1. 双指针初始化设置左指针 l 指向字符串开头右指针 r 指向字符串末尾2. 相向遍历匹配如果 s[l] s[r] 则同时移动左右指针继续向中间匹配3. 遇到不匹配字符此时有两种选择删除左指针字符或删除右指针字符只要其中一种能让剩余子串成为回文串结果就为 true4. 辅助函数校验写一个辅助函数 isPalindrome 专门判断指定区间的子串是否为回文串样例原理讲解以 abca 为例- 初始 l0, r3 s[0] a 、 s[3] a 匹配成功指针移动- 此时 l1, r2 s[1] b 、 s[2] c 不匹配- 尝试删除右指针字符 c 校验子串 aba 是回文串直接返回 trueC完整AC代码实现class Solution {public:bool isPalindrome(const string s, int l, int r) {while(l r) {if(s[l] ! s[r]) return false;l;r--;}return true;}bool validPalindrome(string s) {int l 0, r s.size() - 1;while(l r) {if(s[l] ! s[r]) {return isPalindrome(s, l1, r) || isPalindrome(s, l, r-1);}l;r--;}return true;}};算法考点总结这道题的时间复杂度为O(n)空间复杂度为O(1)是最优解法。核心技巧在于遇到不匹配时用贪心思想直接尝试两种删除路径无需暴力枚举所有删除位置极大提升了效率。回文类题目是算法笔试的常客这道题的双指针辅助校验模板也可以直接套用到其他回文相关的进阶题目中。