LeetCode680. 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:

1
2
Input: "aba"
Output: True

Example 2:

1
2
3
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.

680

跟[125] 验证回文串 思路一样,只不过可以删字符,所以当字符不同的时候,左指针右移一格或者右指针左移一格,如果存在一种可能是回文的情况,就返回真。

Two Pointers

my code in cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool validPalindrome(string s) {
int l=0,r=s.size()-1;
while(l<r){
if(s[l]!=s[r]) return helper(s,l,r-1)||helper(s,l+1,r);
l++,r--;
}
return true;
}

bool helper(string s, int l,int r)
{
while(l<r)
if(s[l++]!=s[r--]) return false;
return true;
}
Thanks for Support.