680.Valid Palindrome II

Tags: Easy String Two Poointers

Links: https://leetcode.com/problems/valid-palindrome-ii/

---

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

---

class Solution {
public:
    bool validPalindrome(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = s.size(); 
        int start = 0, end = n - 1;
        while (start < end) {
            if (s[start] != s[end]) 
                return isPalindrome(s, start + 1, end) || isPalindrome(s, start, end - 1);
            ++start; --end;
        }

        return true;
    }

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

双指针模拟，时间复杂度$O(n)$，空间复杂度$O(1)$。