Valid Palindrome II
- 2 min read
- LC-Easy
- Two Pointers
3 years ago
Solution
- Start from both ends, and whenever the characters are not equal, we need to consider two possible cases:
-
- Check if rest of the string after skipping the left pointer is a palindrome
-
- Check if the rest of the string after skipping the right pointer is a palindrome
-
- We need to check both substrings because there is really no way to check which character to increment
- When we're at this position, we can immediately return True if either one of the two substrings are a palindrome, and if they aren't, we can immediately return False since we already technically removed two characters while we're only allowed to remove 1
| Time | Space | Explanation |
|---|---|---|
O(n) | O() |
def validPalindrome(self, s: str) -> bool:
def is_palindrome(l, r):
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
if is_palindrome(l + 1, r) or is_palindrome(l, r - 1):
return True
return False
l += 1
r -= 1
return True