[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:

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 < 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 < (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 < s.length() / 2; ++i) {
if (s[i] != s[s.length() – i – 1]) {
if (!isValid(s, i + 1, s.length() – i – 1) && !isValid(s, i, s.length() – i -2)) return false;
break;
}
}
return true;
}
};
[/code]