680. 验证回文串 II

难度：简单

题目

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

输入：s = "aba"

输出：true

示例 2：

输入：s = "abca"

输出：true

解释：你可以删除字符 'c' 。

示例 3：

输入：s = "abc"

输出：false

提示：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成

Reference

题解

首先使用双指针法判断是否回文串，当遇到不同字符的时候，分别判断只删除左侧字符和只删除右侧字符，剩下的字符串是否回文串。只要有一个字符串是回文串就满足条件

class Solution:
    def check(self, s: str):
        return s[::-1] == s

    def validPalindrome(self, s: str) -> bool:
        l, r, flag = 0, len(s), True
        if self.check(s):
            return True

        while l < r:
            if s[l] != s[r - 1]:
                return self.check(s[l + 1:r]) or self.check(s[l: r - 1])

            l += 1
            r -= 1
        return True

评论