題目描述：給定非空串S，是否能在最多刪除一個(gè)字符的條件下使得原串變?yōu)榛匚拇?br> 如：
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
分析：開(kāi)始的想法是遍歷字符串李茫，刪除每個(gè)字符看是否構(gòu)成回文串十电，以及原本是否是回文串知押。復(fù)雜度O(n^2)，超時(shí)鹃骂。這種方法會(huì)重復(fù)遍歷很多次已判斷過(guò)的情況台盯，降低復(fù)雜度就要通過(guò)一次遍歷完成判斷，時(shí)間復(fù)雜度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 --;
//出現(xiàn)左右不等時(shí)，檢查要么左邊刪一個(gè)寝殴，要么右邊刪一個(gè)的情況是否可滿足回文
return is(s, i + 1, j) || is(s, i, j - 1);
}
};
