Sponsored
Sponsored
This approach uses the two-pointer technique to check if the string is a palindrome after removing at most one character. Start with two pointers at the beginning and end of the string. Move inward while the characters at these pointers are equal. If a mismatch occurs, there are two possibilities: either remove the character at the left pointer or the right pointer. If either results in a palindrome, then the string can be considered a valid palindrome after one deletion.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) as we use a constant amount of extra space.
1class Solution:
2 def isPalindromeRange(self, s: str, i: int, j: int) -> bool:
3 return all(s[k] == s[j] for k, j in zip(range(i, j), range(j, i, -1)))
4
5 def validPalindrome(self, s: str) -> bool:
6 left, right = 0, len(s) - 1
7 while left < right:
8 if s[left] != s[right]:
9 return self.isPalindromeRange(s, left + 1, right) or self.isPalindromeRange(s, left, right - 1)
10 left += 1
11 right -= 1
12 return TrueIn the Python version, the solution uses a helper function to check if a segment of the string is a palindrome. We then handle mismatches by removing either the left or right character.
This approach uses recursion to accomplish the same task. When encountering the first differing pair of characters, we make two recursive calls: one ignoring the left character and one ignoring the right character. If either recursive call results in a valid palindrome, the whole string can be considered a valid palindrome after a single character deletion.
Time Complexity: O(n)
Space Complexity: O(1) by avoiding deep recursive stacks through tail optimization.
1
The C solution applies a helper function that manages recursive calls whenever a mismatched pair of characters is found, implementing an efficient recursive resolution.