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
思路
还没看到更好的思路