Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
(给定非空字符串s,您最多可以删除一个字符。 判断是否可以成为回文)
样例
Given s = "aba" return true
Given s = "abca" return true // delete c
解:考虑到有两种情况(以下字符串的空格间隔是为了方便区分看)
1)string s="a b d b c a" 这里应该删掉s[4];
- string s="a c b d b a" 这里应该删掉s[1];
bool validPalindrome(string &s) {
// Write your code here
int h=s.length()-1;
int l=0;
bool work=false;
if(h<=1)
return true;
while(l<h)
{
if(s[l]==s[h])
{
l++;
h--;
}
else
{
if(work==false)//因为最多只能删除一个,所以这里用个bool来判别执行一次
{
if(s[l]==s[h-1]) //上面所说的情况一
{
h-=2;
l++;
}
else if(s[l+1]==s[h])//情况二
{
l+=2;
h--;
}
work=true;//删除一次后,设置为true,因为至多删除一个
}
else
return false;
}
}
return true;
}
网友评论