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 <= 105sconsists 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).