# [LeetCode]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.

## 思路

```for (int i = 0; i &lt; s.length(); ++i) {
if (s[i] != s[s.length() - 1 - i]) return false;
}
return true;
```

## 代码

```class Solution {
public:
bool isValid(string s, int start, int end) {
for (int i = start; i &lt; (end - start + 1) / 2 + start; ++i) {
if (s[i] != s[end - (i - start)]) return false;
}
return true;
}
bool validPalindrome(string s) {
for (int i = 0; i &lt; s.length() / 2; ++i) {
if (s[i] != s[s.length() - i - 1]) {
if (!isValid(s, i + 1, s.length() - i - 1) &amp;&amp; !isValid(s, i, s.length() - i -2)) return false;
break;
}
}
return true;
}
};
```

## 技巧

• 由于只有两个分支，所以没有必要利用栈来实现回溯法。
• 在产生两个子字符串时，可以使用两个指针来指定子字符串的范围，而不是使用substr来分隔，并产生一些拷贝。