> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/valid-palindrome/valid-palindrome-ii.md).

# Valid Palindrome II

https\://leetcode.com/problems/valid-palindrome-ii/description/

> 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:
>
> The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

## Thoughts

问给定字符串至多删去一个字符能否构成回文。只有一个字符不满足的话当遇到那个字符时跳过它就还是palindrome，跳过的方式有从左或右跳过。

## Code

```cpp
/*
 * @lc app=leetcode id=680 lang=cpp
 *
 * [680] Valid Palindrome II
 */

// @lc code=start
class Solution {
public:
    bool validPalindrome(string s) {
        const auto palind = [&](int l, int r) {
            while (l < r) {
                if (s[l] != s[r]) return false;
                else {
                    ++l;
                    --r;
                }
            }
            return true;
        };
        for (int l = 0, r = s.length() - 1; l < r; ++l, --r) {
            if (s[l] != s[r]) {
                return palind(l + 1, r) || palind(l, r - 1);
            }
        }
        return true;
    }
};
// @lc code=end


```

```java
class Solution {
    private boolean isPalin(String s, int start, int end) {
        for (; start < end; start++, end--) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
        }
        return true;
    }

    public boolean validPalindrome(String s) {
        for (int l = 0, r = s.length() - 1; l < r; l++, r--) {
            if (s.charAt(l) == s.charAt(r)) {
                continue;
            } else {
                return isPalin(s, l + 1, r) || isPalin(s, l, r - 1);
            }
        }

        return true;
    }
}
```

## Analysis

时间O(N).