给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:

  1. 输入: "aba"
  2. 输出: True

示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。

注意:

  1. 字符串只包含从 a-z 的小写字母。字符串的最大长度是 50000 。

1. 超时的做法：

题目问我们最多删除一个字符的情况下是否可以构成回文字符串，第一反应是逐个删除各个字符看剩下的字符串是否为回文串，但是这个时间复杂度是 O(N ^ 2) ，题目给出的字符串的长度最大为 50000 ，此做法会超时。

代码

class Solution {
public:
    bool validPalindrome(string s) {
        if (s.size() == 1) return true;
        else if (s.size() == 0) return false;

        if (isPalindrome(s)) {
            return true;
        }
        else {
            for (int i = 0; i < s.size(); i++) {
                string tempStr = s;

                tempStr.erase(tempStr.begin() + i);
                if (isPalindrome(tempStr)) {
                    return true;
                }
            }
        }

        return false;
    }

    bool isPalindrome(string str) {
        if (str.size() == 1) return true;
        else if (str.size() == 0) return false;

        int totalIndex = str.size() - 1;
        for (int i = 0; i < totalIndex / 2 + 1; i++) {
            if (str[i] != str[totalIndex - i]) {
                return false;
            }
        }
        return true;
    }

};

2. 改进的做法

回文串的特点是左右对称。假如有两个指针从字符串的两端同时向中间走：如果遇到的元素相等，则该相等的元素是最终回文字符串的一部分；如果遇到的元素不等，则认为此时遇到了构建回文字符串的「障碍」，应当进行处理，处理方式见下文。

  • 分析一下 例2：

    输入: "abca"
输出: True
解释: 你可以删除c字符。

  • 如果左右指针从两端同时向中间走，那么： ``` 第一步： a b c a | | left right

第二步： a b c a | | left right

第一步，左右指针遇到的元素相等，继续向中间走；<br />第二步，左右指针遇到的元素不等，则必须进行处理：我们必须删除其中的一个字符，然后再判断 **剩余的所有字符** 是否是回文串。

删除 b： a c a

或者， 删除 c： a b a


即判断 `aca`  或者 `aba`  是否为回文字符串。

如果删除一个字符后，剩余的全部字符构成字符串 是回文字符串，那么就满足题意。

本方案的时间复杂度是： `O(N)` ；由于我判断是否回文使用了新建的字符串，所以空间复杂度是 `O(N)` 。

<a name="E8kZ9"></a>
#### 代码
```cpp
class Solution {
public:
    bool validPalindrome(string s) {
        if (s.size() == 1) return true;
        else if (s.size() == 0) return false;

        int totalIndex = s.size() - 1;
        int left;
        int right;
        for (int i = 0; i < totalIndex / 2 + 1; i++) {
            left = i;
            right = totalIndex - i;
            // 加入左边 != 右边
            if (s[left] != s[right]) {
                string strLeft = s;
                string strRight = s;

                strLeft.erase(strLeft.begin() + left);
                strRight.erase(strRight.begin() + right);

                if (isPalindrome(strLeft) || isPalindrome(strRight) ) {
                    return true;
                }
                else
                    return false;
            }
        }

        return true;

    }

    bool isPalindrome(string str) {
        if (str.size() == 1) return true;
        else if (str.size() == 0) return false;

        int totalIndex = str.size() - 1;
        for (int i = 0; i < totalIndex / 2 + 1; i++) {
            if (str[i] != str[totalIndex - i]) {
                return false;
            }
        }
        return true;
    }

};