## 原题

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.

## 思路

[code lang=”cpp”]
for (int i = 0; i &lt; s.length(); ++i) {
if (s[i] != s[s.length() – 1 – i]) return false;
}
return true;
[/code]

## 代码

[code lang=”cpp”]
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;
}
};
[/code]

## 技巧

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

Share:

This site uses Akismet to reduce spam. Learn how your comment data is processed.