680. Valid Palindrome II

题目描述：给定非空串S，是否能在最多删除一个字符的条件下使得原串变为回文串。
如：

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

分析：开始的想法是遍历字符串，删除每个字符看是否构成回文串，以及原本是否是回文串。复杂度O(n^2)，超时。这种方法会重复遍历很多次已判断过的情况，降低复杂度就要通过一次遍历完成判断，时间复杂度O(n)，空间O(1)。

代码：

class Solution {
public:
    //判断子串str是否回文
    bool is(string str, int l, int r)
    {
        while (l < r && str[l] == str[r])
            l ++, r --;
        return l >= r;
    }
    bool validPalindrome(string s) {

        int l = s.length();
        int i = 0, j = l - 1;
        while(i < j && s[i] == s[j])
            i ++, j --;
        //出现左右不等时，检查要么左边删一个，要么右边删一个的情况是否可满足回文
        return is(s, i + 1, j) || is(s, i, j - 1);
    }
};