valid-palindrome-ii

Valid Palindrome II – LeetCode 680

Problem

Description

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
bool validPalindrome(string s) {
int l = 0, r = s.size() - 1;
bool flag = true;
while(l <= r){
if(s[l] == s[r]){
++l;
--r;
} else if(flag){
++l;
flag = false;
} else
break;
}
if(r >= l){
l = 0; r = s.size() - 1;
flag = true;
while(l <= r){
if(s[l] == s[r]){
++l;
--r;
} else if(flag){
--r;
flag = false;
} else
break;
}
return r < l;
} else
return true;
}
};

思路

通过枚举删除字符的两种情况来得到答案。时间复杂度$O(n)$,空间复杂度$O(1)$。
耗时$84$ ms,排名$72.49\%$

Better

思路

还没看到更好的思路