LeetCode 680. Valid Palindrome II

Description

https://leetcode.com/problems/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.

Explanation

Use two pointers technique. One pointer starts from the beginning, one starts from the end. Whenever two pointers found two unmatched characters, skip the character from either side to see if the remaining parts fits the palindrome requirement.

Python Solution

class Solution:
    def validPalindrome(self, s: str) -> bool:
        
        i = 0
        j = len(s) - 1
        
        
        while i < j:
            if s[i] == s[j]:
                i += 1
                j -= 1
            else:
                return self.helper(s, i + 1, j) or self.helper(s, i, j - 1)

                
        return True
    
    def helper(self, s, left, right):
        
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return False
        
        return True
            
        
  • Time Complexity: O(N).
  • Space Complexity: O(1).

Leave a Reply

Your email address will not be published.