題目描述

給你一個字符串?s，最多?可以從中刪除一個字符。

請你判斷?s?是否能成為回文字符串：如果能，返回?true?；否則，返回?false?。

示例 1：

輸入：s = "aba"
輸出：true

示例 2：

輸入：s = "abca"
輸出：true
解釋：你可以刪除字符 'c' 。

示例 3：

輸入：s = "abc"
輸出：false

提示：

• 1 <= s.length <= 105
• s?由小寫英文字母組成

解決方案：

1、首尾向內收縮遍歷：會出現刪除左字符還是右字符的問題，解決：先假設刪除一邊

2、檢查函數：檢查刪除后，剩余的字符是否符合題意

3、取或：討論兩種狀態下，只要滿足一個即可，故用或運算。

函數源碼：

class Solution {
public:bool check(const string& s, int l, int r) {for (int i = l, j = r; i < j; i++, j--) {if (s[i] != s[j]) {return false;}}return true;}bool validPalindrome(string s) {int l = 0, r = s.size() - 1;while (l < r) {char c1 = s[l], c2 = s[r];if (c1 == c2) {l++;r--;} else {return check(s, l, r - 1) || check(s, l + 1, r);}}return true;}
};