125. Valid Palindrome
Model: qwen2.5-coder:14b
Topics: Two Pointers,String
FAANG asked: 1
Acceptance rate: 38.5%
Problem Breakdown
The problem asks us to determine if a given string s is a palindrome, considering only alphanumeric characters and ignoring cases. A palindrome is a sequence that reads the same backward as forward.
Inputs:
- A single string
s.
Outputs:
- A boolean value indicating whether the string is a palindrome or not.
Implicit Constraints/Edge Cases:
- The string may contain non-alphanumeric characters (e.g., spaces, punctuation) which should be ignored.
- The comparison should be case-insensitive.
- An empty string or a single character string should return
trueas they are trivially palindromes. - Strings with only non-alphanumeric characters should also return
true.
Intuition
A brute-force approach would involve removing all non-alphanumeric characters, converting the string to lowercase, and then checking if the resulting string is equal to its reverse. This approach has a time complexity of O(n) for cleaning the string and another O(n) for reversing it, making it O(2n) or simply O(n). However, this can be optimized.
The key insight is that we don’t need to create a new cleaned string. Instead, we can use two pointers: one starting at the beginning of the string and the other at the end. We move these pointers towards each other, skipping non-alphanumeric characters and comparing the alphanumeric characters in a case-insensitive manner. This approach reduces the space complexity to O(1) since we are not using any additional data structures.
Approach
- Initialize two pointers:
leftstarting at the beginning of the string andrightstarting at the end. - Move the
leftpointer to the right until it points to an alphanumeric character or crosses therightpointer. - Move the
rightpointer to the left until it points to an alphanumeric character or crosses theleftpointer. - Compare the characters at the
leftandrightpointers in a case-insensitive manner. - If they are not equal, return
false. - If they are equal, move both pointers towards each other and repeat steps 2-5.
- If the loop completes without finding any mismatched characters, return
true.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. Each character is checked at most once.
- Space Complexity: O(1). No additional space is used other than a few variables for pointers and temporary storage.
Solution
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
# Move the left pointer to the next alphanumeric character
while left < right and not s[left].isalnum():
left += 1
# Move the right pointer to the previous alphanumeric character
while left < right and not s[right].isalnum():
right -= 1
# Compare characters in a case-insensitive manner
if s[left].lower() != s[right].lower():
return False
# Move both pointers towards each other
left += 1
right -= 1
return True
Edge Cases Handled
- Empty String: The loop condition
left < rightensures that the function returnstrueimmediately. - Single Character String: Similar to the empty string case, the loop will not execute and
trueis returned. - Strings with Only Non-Alphanumeric Characters: Both pointers will eventually cross each other without finding any mismatched characters, resulting in a return value of
true. - Mixed Case Strings: The comparison is done in lowercase, ensuring case insensitivity.