680. 驗證回文字元串 Ⅱ
難度簡單311
給定一個非空字元串
s
,最多删除一個字元。判斷是否能成為回文字元串。
示例 1:
示例 2:輸入: "aba" 輸出: True
注意:輸入: "abca" 輸出: True 解釋: 你可以删除c字元。
- 字元串隻包含從 a-z 的小寫字母。字元串的最大長度是50000。
雙指針法
因為這有可能需要删除一個字母,是以我們把驗證是否是回文串寫進一個函數裡面。還是按之前的雙指針方法判斷字母是否相同,如果遇到一個不相同時,此時就出現了可能需要删除的字母。
但删除次數隻有一個,要麼是目前左指針或右指針,是以在這裡調用之前寫好的回文串check函數,把索引相應的寫入即可。這樣的好處是用函數的參數索引可以同時判斷兩個位置的字母是否需要删除。
class Solution {
public:
bool validPalindrome(string s) {
int left = 0, right = s.length()-1;
while(left < right){
if(s[left] == s[right]){
left++;
right--;
}
else{
return check(s, left+1, right) || check(s, left, right-1);
}
}
return true;
}
bool check(string& s, int left, int right){
while(left < right){
if(s[left] != s[right]){
return false;
}
left++;
right--;
}
return true;
}
};