###### tags: `Leetcode` `easy` `pointer` `python` `c++`

# 680. Valid Palindrome II

## [題目連結:] https://leetcode.com/problems/valid-palindrome-ii/

## 題目:
Given a string ```s```, return ```true``` if the ```s``` can be palindrome after deleting **at most one** character from it.

**Example 1:**

Input: s = "aba"
Output: true

**Example 2:**

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

**Example 3:**

Input: s = "abc"
Output: false

## 解題想法:
* 題目為判斷字串是否符合回文:
* 可以有一個字符不正確的扣打
* 只有two pointer指向頭尾:
* head=0
* tail=len(s)-1
* 若s[head]!=s[tail]
* 則判斷兩種case:
* 扣打給head: 求head+1~tail是否合法
* 扣打給tail: 求head~tail-1是否合法
* 否則正常內縮判斷
* head+=1
* tail-=1

## Python:

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        head=0
        tail=len(s)-1
        count=0
        while head<=tail:
            if s[head]!=s[tail]:
                return self.valid(s,head+1,tail) or self.valid(s,head,tail-1)
            else:
                head+=1
                tail-=1
        return True
    def valid(self,s,head,tail):
        while head<=tail:
            if s[head]!=s[tail]:
                return False
            head+=1
            tail-=1
        return True

if __name__=='__main__':
    result=Solution()
    ans=result.validPalindrome(s = "abca")
    print(ans)

## C++:

#include<iostream>
using namespace std;

class Solution {
public:
    bool validPalindrome(string s) {
        int head=0;
        int tail=s.size()-1;
        while (head<=tail){
            if (s[head]!=s[tail])
                return valid(s,head+1,tail) || valid(s,head,tail-1);
            head+=1;
            tail-=1;
        }
        return true;
    }
    bool valid(string s, int head, int tail){
        while (head<=tail){
            if (s[head]!=s[tail])
                return false;
            head+=1;
            tail-=1;
        }
        return true;
    }
};

int main(){
    Solution res;
    string s="abca";
    bool ans=res.validPalindrome(s);
    cout<<ans<<endl;
    return 0;
}