680. Valid Palindrome II

O(n) 两个指针l和r从外往内扫描，如果遇到两个字符s[l]和s[r]不一样，则分别判断s[l:r-1]和s[l+1:r]是不是回文串

class Solution {
public:
    bool validPalindrome(string s) {
        for (int n = s.length(), l = 0, r = n - 1; l < r; ++l, --r) {
            if (s[l] != s[r]) {
                return isPalin(s, l, r - 1) || isPalin(s, l + 1, r);
            }
        }
        return true;
    }

    bool isPalin(const string &s, int l, int r) {
        while (l < r) {
            if (s[l++] != s[r--]) return false;
        }
        return true;
    }
};

O(n)

class Solution {
public:
    bool validPalindrome(string s) {
        int n = s.length();
        int l = 0, r = n - 1;
        int cnt1 = 0;
        while (l < r) {
            if (s[l] != s[r]) {
                ++cnt1;
                if (cnt1 > 1) break;
                if (s[l + 1] == s[r]) {
                    ++l;
                } else if (s[l] == s[r - 1]) {
                    --r;
                } else {
                    return false;
                }
            }
            ++l;
            --r;
        }
        l = 0, r = n - 1;
        int cnt2 = 0;
        while (l < r) {
            if (s[l] != s[r]) {
                ++cnt2;
                if (cnt2 > 1) break;
                if (s[l] == s[r - 1]) {
                    --r;
                } else if (s[l + 1] == s[r]) {
                    ++l;
                } else {
                    return false;
                }
            }
            ++l;
            --r;
        }
        return cnt1 < 2 || cnt2 < 2;
    }
};