# 680. Valid Palindrome II 验证回文字符串 Ⅱ

@TOC

## # 题目描述

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.

## # 解题方法

### # 初版方案

``````输入: "abca"

``````

``````第一步：
a       b       c       a
|                       |
left                  right

a       b       c       a
|       |
left  right
``````

``````删除 b：
a       c       a

a       b       a
``````

Python 代码如下。

``````class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
isPalindrome = lambda s: s == s[::-1]
strPart = lambda s, x: s[:x] + s[x + 1:]
left = 0
right = len(s) - 1
while left < right:
if s[left] != s[right]:
return isPalindrome(strPart(s, left)) or isPalindrome(strPart(s, right))
left += 1
right -= 1
return True

``````

### # 进阶方案

`(left, right]` 或者 `[left, right)` 为回文串，则说明删除了一个字符可以构成回文串。

Python 代码如下。

``````class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
isPalindrome = lambda x : x == x[::-1]
left, right = 0, len(s) - 1
while left <= right:
if s[left] == s[right]:
left += 1
right -= 1
else:
return isPalindrome(s[left + 1 : right + 1]) or isPalindrome(s[left: right])
return True
``````

## # 日期

2018 年 2 月 4 日 2018 年 11 月 24 日 —— 周日开始！一周就过去了～ 2020 年 5 月 19 日 —— 希望工作效率更高