Valid Palindrome Check
Check if a given string s is a palindrome (reads the same forwards and backward), ignoring case and non-alphanumeric characters.
Examples:
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After removing non-alphanumeric characters and converting to lowercase,
it becomes "amanaplanacanalpanama", which is a palindrome.
Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:
Input: s = " "
Output: true
Explanation: An empty string (after filtering) is considered a palindrome.
Constraints:
1 <= len(s) <= 2 * 105sconsists only of printable ASCII characters.
Function Signature (Python):
class Solution:
def isPalindrome(self, s: str) -> bool:
# Your code here
pass
Related Python Concepts
Hint
A palindrome needs to be checked after some "cleaning". Think about:
- Preprocessing: How can you transform the input string so that only relevant characters are considered, and case differences don't matter? (e.g., "RaceCar!" should be treated as "racecar").
- Comparison Strategy: Once you have the "cleaned" string, how can you efficiently check if it reads the same forwards and backward?
- Consider comparing characters from opposite ends, moving inwards.
- Alternatively, what if you compared the cleaned string to its reversed version?
- Edge Cases: What about an empty string or a string with only one character after cleaning? Are these palindromes? (Yes, by common definition).
Solution Explanation & Interview Strategy
The Goal: Check if a string like "A man, a plan, a canal: Panama" is a palindrome. This means it should read the same forwards and backwards, but we must first ignore punctuation, spaces, and letter casing.
So, "A man, a plan, a canal: Panama" first becomes "amanaplanacanalpanama". Then we check if this cleaned string is a palindrome.
In an interview, clearly stating the preprocessing steps is as important as the palindrome check itself.
Approach 1: Preprocess then Two-Pointer (Often Preferred in Interviews)
This is a robust approach that clearly separates concerns: first cleaning the string, then applying a standard palindrome-checking algorithm.
Step 1: Preprocessing the String
We need to iterate through the original string, convert each character to lowercase, and keep only the alphanumeric characters.
Step 2: Two-Pointer Check
Once we have the cleaned string (or a list of its characters), we use two pointers, one starting at the beginning (left) and one at the end (right). We compare the characters at these pointers. If they are ever different, it's not a palindrome. If they match, we move left one step to the right and right one step to the left, and repeat until the pointers meet or cross.
class Solution:
def isPalindrome_two_pointer(self, s: str) -> bool:
# Step 1: Preprocess the string
cleaned_chars = []
for char in s:
if char.isalnum(): # Check if character is alphanumeric
cleaned_chars.append(char.lower()) # Convert to lowercase and add
# Alternative using a generator expression and join (more Pythonic for cleaning)
# cleaned_string = "".join(char.lower() for char in s if char.isalnum())
# if not cleaned_string: return True # Empty string is a palindrome
# left, right = 0, len(cleaned_string) - 1
# while left < right:
# if cleaned_string[left] != cleaned_string[right]:
# return False
# ... rest of logic for cleaned_string ...
if not cleaned_chars: # Handles empty string or string with no alphanumeric chars
return True
# Step 2: Two-pointer check on the list of cleaned characters
left, right = 0, len(cleaned_chars) - 1
while left < right:
if cleaned_chars[left] != cleaned_chars[right]:
return False
left += 1
right -= 1
return True
# Example Usage:
# sol = Solution()
# print(sol.isPalindrome_two_pointer("A man, a plan, a canal: Panama")) # Output: True
# print(sol.isPalindrome_two_pointer("race a car")) # Output: False
- Preprocessing: "Race car!" ->
['r', 'a', 'c', 'e', 'c', 'a', 'r']. - Two Pointers on
cleaned_chars:left=0('r'),right=6('r'). Match.left=1, right=5.left=1('a'),right=5('a'). Match.left=2, right=4.left=2('c'),right=4('c'). Match.left=3, right=3.
left(3) is not less thanright(3). Loop terminates. ReturnTrue.
Complexity Analysis:
Time Complexity: O(N), where N is the length of the original string.
- Preprocessing: Iterating through the string once to filter and convert characters is O(N). Appending to
cleaned_charsis O(1) on average per character. - Two-Pointer Check: This iterates at most M/2 times, where M is the length of the cleaned string (M <= N). So, this step is O(M), which is O(N).
Space Complexity: O(M) or O(N) in the worst case, for cleaned_chars (if all characters are alphanumeric). If we optimize the two-pointer check to work directly on the input string by skipping non-alphanumeric characters (more complex pointer logic), space could be O(1).
Approach 2: Preprocess then Compare with Reversed String
This approach also starts by cleaning the string. Then, it compares the cleaned string with its reversed version. This is often very concise in Python.
class Solution:
def isPalindrome_compare_reversed(self, s: str) -> bool:
# Step 1: Preprocess the string (Pythonic one-liner)
cleaned_string = "".join(char.lower() for char in s if char.isalnum())
# Step 2: Compare with its reversed version
return cleaned_string == cleaned_string[::-1]
# Example Usage:
# sol = Solution()
# print(sol.isPalindrome_compare_reversed("A man, a plan, a canal: Panama")) # True
- Preprocessing: "Race car!" ->
cleaned_string= "racecar". - Reverse
cleaned_string: "racecar"[::-1]-> "racecar". - Compare: "racecar" == "racecar" is
True.
Complexity Analysis:
Time Complexity: O(N).
- Preprocessing (
joinwith generator expression): O(N). - Slicing to reverse (
[::-1]): O(M) where M is length of cleaned string. - String comparison: O(M).
Space Complexity: O(M) or O(N) for cleaned_string and its reversed copy created during slicing for comparison.
Approach 3: Optimized Two-Pointer (In-Place Character Skipping)
This is a more advanced variation that avoids creating an intermediate cleaned string, potentially saving space. The pointers skip non-alphanumeric characters directly in the original string.
class Solution:
def isPalindrome_optimized_pointers(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
# Move left pointer to the next alphanumeric character
while left < right and not s[left].isalnum():
left += 1
# Move right pointer to the previous alphanumeric character
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Complexity Analysis:
Time Complexity: O(N). Each character is visited at most twice by the pointers.
Space Complexity: O(1), as we are not creating any new data structures proportional to the input string size. This is a significant advantage if memory is a concern.
Key Takeaways for Interviews:
- Clarify Requirements: Always start by asking about case sensitivity and handling of non-alphanumeric characters. This problem explicitly states them.
- Preprocessing is Key: Clearly articulate the need to "clean" the string.
- Show how to filter characters (e.g., using
isalnum()) and convert case (e.g., usinglower()).
- Show how to filter characters (e.g., using
- Prioritize Algorithmic Thinking:
- The two-pointer approach (Approach 1 or Approach 3) is generally well-received as it demonstrates good algorithmic understanding. Approach 3 is more space-efficient.
- Discussing the trade-offs (e.g., Approach 1 is conceptually simpler due to separate cleaning, Approach 3 is more space-efficient but has more complex pointer logic) is valuable.
- Pythonic Solutions as Alternatives: Approach 2 (comparing cleaned string with its slice-reversed version) is very Pythonic and concise. You can mention it after demonstrating a more manual method.
- Handle Edge Cases: Consider empty strings, strings with only non-alphanumeric characters, or single-character strings. The problem states
len(s) >= 1, but an empty string after cleaning is still a valid case to consider (and is a palindrome).