0680：验证回文串 II

力扣第 680 题

题目

给你一个字符串 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
4
5
6
7
8
9

def validPalindrome(self, s: str) -> bool:
	if s == s[::-1]:
		return True
	l, r = 0, len(s) - 1
	while l < r and s[l] == s[r]:
		l += 1
		r -= 1
	a, b = s[l+1:r+1], s[l:r]
	return a==a[::-1] or b==b[::-1]

时间复杂度 O(N)，64 ms