algoadvance

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Clarifying Questions

1. Input Format: Can the input string contain spaces and punctuation?
   • Yes, any string may include spaces, punctuation, and other non-alphanumeric characters.
2. Output Format: Do I return a boolean value?
   • Yes, return True if the input string is a palindrome, otherwise return False.
3. Case Sensitivity: Should the comparison be case-insensitive?
   • Yes, treat uppercase and lowercase letters as the same character.

Strategy

1. Filtering and Normalization:
   • First, filter out non-alphanumeric characters from the string.
   • Convert all characters to lowercase to ensure the comparison is case-insensitive.
2. Palindrome Check:
   • Check if the filtered and normalized string reads the same forwards and backwards.

Code

def isPalindrome(s: str) -> bool:
    # Remove non-alphanumeric characters and convert to lowercase.
    filtered_chars = [char.lower() for char in s if char.isalnum()]
    
    # Check if the processed characters form a palindrome.
    return filtered_chars == filtered_chars[::-1]

# Example usage
print(isPalindrome("A man, a plan, a canal: Panama"))  # Output: True
print(isPalindrome("race a car"))                     # Output: False

Time Complexity

• Filtering and Normalization: This operation iterates through each character of the string, so its time complexity is (O(n)), where (n) is the length of the string.
• Palindrome Check: Comparing the list to its reversed version also takes (O(n)) time.

Thus, the overall time complexity of the solution is (O(n)).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?