LeetCode

Appearance

680 Valid Palindrome II ​

题目 ​

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

 

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.
Related Topics
  • 贪心
  • 双指针
  • 字符串

  • 👍 703
  • 👎 0

    • 解法 ​

    双指针判断是否是回文串，当忽略一个元素时，需要分而治之去分别判断是否是回文串

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(s) -> bool:
            left = 0
            right = len(s) - 1
            while left < right:
                if s[left] == s[right]:
                    left += 1
                    right -= 1
                else:
                    return False
            return True

        left = 0
        right = len(s) - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return is_palindrome(s[left:right]) or is_palindrome(s[ left+1: right+1])

        return True
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度O(N)
    • 空间复杂度O(1)