Skip to main content

680. Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/

Python​

Brute Force (Timelimit Exceed)​

  • Time: O(N^2)
  • Space: O(NlogN)
class Solution:
    def validPalindrome(self, s: str) -> bool:
        for i in range(len(s)):
            remains = s[:i] + s[i+1:]
            if remains == remains[::-1]:
                return True
        return False

Scan from begin and end in 2nd level (Timelimit Exceed)​

  • Time: O(NlogN)
  • Space: O(NlogN)
class Solution:
    def validPalindrome(self, s: str) -> bool:
        if self.isPalindrome(s):
            return True

        for i in range(len(s)):
            if self.isPalindrome(s[:i] + s[i+1:]):
                return True

        return False

    # Leetcode 125
    def isPalindrome(self, s: str) -> bool:
        if len(s) < 2:
            return True

        for i in range(len(s)//2):
            if s[i] != s[len(s)-1-i]:
                return False

        return True

Two Pointers​

做第一層的palindrome check時，其實只要invalid了，若刪一個還能valid的話，該刪除的character勢必是在當下的左界或右界。利用這個特性達成O(N)的Time complexity

  • Time: O(N)
  • Space: O(1)
class Solution:
    def validPalindrome(self, s: str) -> bool:
        left, right = 0, len(s)-1

        while left < right:
            if s[left] != s[right]:
                return self.isPalindrome(s, left+1, right) or self.isPalindrome(s, left, right-1)
            left += 1
            right -= 1

        return True

    def isPalindrome(self, s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1

        return True