題目描述:
Given a non-empty string?s
, you may delete?at most?one character. Judge whether you can make it a palindrome.
leetcode 340?Example 1:
Input: "aba"
Output: True
?
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
?
Note:
- The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
?
要完成的函數:
bool validPalindrome(string s)?
?
說明:
1、給定一個字符串,至多刪去里面的一個字符,使其成為一個回文串。判斷能不能實現。
2、我們先看一個例子
abca
acba(反轉)
我們可以看到第一個字母是一樣的,第二個字母的時候就對不上了,那我們如果要形成一個回文串,可以試著刪去第二個字母b,也可以刪去從后面數起第二個字母c,只要之后能一一對上,那么還是一個回文串。
?
關于這兩種情況,給兩個例子來說明一下:
ececabbacec,這個字符串,我們看到第一個字符e和最后一個字符c沒對上,我們可以刪去e,這樣子能形成回文串。我們也能刪去c,但這樣形成不了回文串。這是要刪去前面字符的例子。
abbca,這個字符串,如果刪去前面字符b,那么形成不了回文串,如果刪去后面字符c,剛好能形成回文串。這是要刪去后面字符的例子。
?
所以我們要分成兩種情況來判斷處理。
按照上述邏輯來處理一下,構造如下代碼:(附解釋)
bool validPalindrome(string s) {int i=0,j=s.size()-1;while(i<j){if(s[i]!=s[j])//當碰到對不上的時候,記錄i和j的值break;i++;j--; }int i1=i,j1=j;//記錄一個副本i++;//如果刪去前面的字符,i++,處理下一個bool flag=1;while(i<j){if(s[i]!=s[j])//如果出現第二次對不上的情況{flag=0;break;}i++;j--;}if(flag==1)//如果全程都對得上,那么返回truereturn true;j1--;//如果刪去前面的字符對不上了,那么刪去后面的字符試試while(i1<j1){if(s[i1]!=s[j1])//如果還是對不上,返回falsereturn false;i1++;j1--;}return true;//如果全程對得上,那么返回true}
上述代碼實測119ms,beats 90.33% of cpp submissions。