Given a string
true if the
s can be palindrome after deleting at most one character from it.
Input: s = "aba" Output: true
Input: s = "abca" Output: true Explanation: You could delete the character 'c'.
Input: s = "abc" Output: false
1 <= s.length <= 105
sconsists of lowercase English letters.
We can use the standard two-pointer approach that starts at the left and right of the string and move inwards. Whenever there is a mismatch, we can either exclude the character at the left or the right pointer. We then take the two remaining substrings and compare them against their reversed and see if either one is a palindrome.
class Solution(object): def validPalindrome(self, s): """ :type s: str :rtype: bool """ # Time: O(n) # Space: O(n) left, right = 0, len(s) - 1 while left < right: if s[left] != s[right]: one, two = s[left:right], s[left + 1:right + 1] return one == one[::-1] or two == two[::-1] left, right = left + 1, right - 1 return True
class Solution: def validPalindrome(self, s): i = 0 j = len(s)-1 while i < j: if s[i] != s[j]: delete_i = s[i+1:j+1] delete_j = s[i:j] return self._isPalindrome(delete_i) or self._isPalindrome(delete_j) i += 1 j -= 1 return True def _isPalindrome(self, s): return s == s[::-1]