【Leetcode】680. Valid Palindrome II（回文字符串）

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True
  

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
  

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

题目大意：

你至多可以删除一个字符串，判断删除后的字符串是否为回文字符串。

解题思路：

双指针，左右分别判断对应位置是否相等。若不等则判断删除其中一个中间的部分是否是回文串即可。

bool isPalindrome(string s, int x, int y){
    while(x<y){
        if(s[x]!=s[y]) return false;
        x++, y--;
    }
    return true;
}

class Solution {
public:
    bool validPalindrome(string s) {
        int i, j;
        i = 0;
        j = s.length()-1;
        while(i<j){
            if(s[i] != s[j]){
                return isPalindrome(s, i+1, j) || isPalindrome(s, i, j-1);
            }
            i++, j--;
        }
        return true;
    }
};