【Leetcode刷题记录】680. 验证回文串 II

给你一个字符串 s，最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

这道题最直观的方法是先判断字符串s是不是回文，如果是直接返回true，如果不是，那么枚举每一个被删除的位置，
判断删除字符后是否是回文，如果是返回true，否则返回false。这种方法的时间复杂度是$O(n^2)$。

    // 辅助函数：判断字符串是否是回文
    bool isPalindrome(const string& s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
 bool validPalindrome(string s) {
        // 先判断是否已经是回文
        if (isPalindrome(s)) {
            return true;
        }
        // 枚举删除每一个字符
        for (int i = 0; i < s.length(); i++) {
            string temp = s;
            temp.erase(i, 1); // 删除第 i 个字符
            if (isPalindrome(temp)) {
                return true;
            }
        }
        return false;
    }

判断字符串是否是回文我们可以使用双指针的方法来求解，定义左右指针left和right来求解，如果$s[left]==s[right]$，那么$left++，right--$，否则返回false。这种方法的时间复杂度是$O(n)$。那么针对这道题，采用双指针解法，当$s[left]!=s[right]$时，两个指针所指的字符必须有一个要删除，我们分别判断删除左指针指向的字符后留下的子串$s[left+1:right]$和删除右指针指向的字符留下的子串$s[left:right-1]$是否是回文，如果有一个是返回true，否则返回false。

// 辅助函数：判断字符串是否是回文
bool check(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            } else {
                left++;
                right--;
            }
        }
        return true;
    }
    bool validPalindrome(string s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l] == s[r]) {
                l++;
                r--;

            } else {
                return check(s,l,r-1)||check(s,l+1,r);
            }
        }
        return true;
    }