目录

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