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