680.Valid Palindrome II
680.Valid Palindrome II
难度:Easy Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
1
Example 1:
2
Input: "aba"
3
Output: True
4
Example 2:
5
Input: "abca"
6
Output: True
7
Explanation: You could delete the character 'c'.
8
Note:
9
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
Copied!
从头尾开始往内遍历,如果直接遍历完是回文返回true,如果遇到不相等的,将左、右分别删掉一个然后分别检查是否是回文字串,如果是返回true,否则返回 false。 时间复杂度O(n)
1
class Solution {
2
bool isValid(int left,int right,string s)
3
{
4
while(left<right)
5
{
6
if(s[left++] != s[right--])
7
return false;
8
}
9
return true;
10
}
11
public:
12
bool validPalindrome(string s) {
13
if(s.length()<3) return true;
14
int left=0;
15
int right=s.length()-1;
16
while(left<right)
17
{
18
if(s[left]!=s[right]) return isValid(left+1,right,s) || isValid(left,right-1,s);
19
left++;
20
right--;
21
22
}
23
return true;
24
}
25
};
Copied!
执行用时 :84 ms, 在所有 C++ 提交中击败了95.29%的用户 内存消耗 :26.1 MB, 在所有 C++ 提交中击败了53.76%的用户
Copy link