Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: "aba" Output: True
Example 2:
Input: "abca" Output: True Explanation: You could delete the character 'c'.
Note:
The description was taken from https://leetcode.com/problems/valid-palindrome-ii/.
#O(N) Time, O(1) Space
class Solution:
def validPalindrome(self, s: str) -> bool:
def palindrome(left:int, right:int) -> bool:
while left < right:
if s[left] == s[right]:
left +=1
right-=1
else:
return False
return True
left, right = 0, len(s) -1
while left < right:
if s[left] == s[right]:
left +=1
right-=1
else:
without_left = palindrome(left + 1, right)
without_right = palindrome(left, right-1)
return without_left or without_right
return TrueSimilar to other palindrome questions, this can be solved by using two pointers.
In each iteration, we will check if the characters at the two pointers are the same. If they are, we will move the pointers inward. If they are not, we will try excluding either the left or the right pointers for our one deletion.
We'll start by creating a traditional palindrome function that uses a while loop to check if the left element matches the right element and moves both pointers inwards if so, returning false if there is a mismatch.
If there was no mismatch, this is a valid palindrome.
def palindrome(left:int, right:int) -> bool:
while left < right:
if s[left] == s[right]:
left +=1
right-=1
else:
return False
return True
What we will do is set our initial left and right pointers at the beginning and end of the string within the validPalindrome function that was given to us.
left, right = 0, len(s) -1
Then, we will continue to compare the two pointers and move them inward if the two characters are equal.
while left < right:
if s[left] == s[right]:
left +=1
right-=1
If not, we will try once more excluding the left pointer, and again excluding the right pointer, then return if either one of these is valid from the singular deletion tried in both function calls.
else:
without_left = palindrome(left + 1, right)
without_right = palindrome(left, right-1)
return without_left or without_right
If we broke from the loop without returning anything, that means that we didn't need to delete any character because the initial string was a valid palindrome.
return True