Palindrome Check: Determining If a String Is a Palindrome

Table of Contents

1. What Is a Palindrome?
2. Problem Statement
3. Algorithm Explanation
4. Python Implementation
5. Example Walkthrough
6. Testing the Solution
7. Conclusion

What Is a Palindrome?

A palindrome is a sequence of characters that reads the same forward and backward. For example, "racecar" and "A man, a plan, a canal: Panama" are palindromes when ignoring spaces, punctuation, and capitalization.

Problem Statement

Given a string, determine if it is a palindrome, considering only alphanumeric characters (letters and numbers) and ignoring cases, spaces, and punctuation. For instance:

• Input: "A man, a plan, a canal: Panama" → Output: True
• Input: "race a car" → Output: False

Algorithm Explanation

To check if a string is a palindrome while ignoring non-alphanumeric characters, follow these steps:

1. Clean the string: Convert to lowercase and filter out non-alphanumeric characters.
2. Use two pointers: Initialize two pointers, one at the start and one at the end of the cleaned string.
3. Compare characters: Move the pointers toward each other, comparing characters. If they mismatch, the string is not a palindrome.
4. Return result: If all comparisons match, the string is a palindrome.

Python Implementation

Below is a Python function to check if a string is a palindrome:

def isPalindrome(s: str) -> bool:
    # Step 1: Clean the string
    cleaned = ''.join(char.lower() for char in s if char.isalnum())

    # Step 2: Use two pointers
    left, right = 0, len(cleaned) - 1

    # Step 3: Compare characters
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1

    # Step 4: Return result
    return True

Example Walkthrough

Let’s test the function with two examples:

1. Input: "A man, a plan, a canal: Panama"
   • Cleaned string: "amanaplanacanalpanama"
   • Comparison: Characters match from both ends → True
2. Input: "race a car"
   • Cleaned string: "raceacar"
   • Comparison: 'r' ≠ 'r' at some point → False

You can run the code as follows:

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

Testing the Solution

To ensure the palindrome check function is robust, comprehensive unit tests are essential. Below is a Python test suite using the unittest framework to validate various cases:

import unittest

def isPalindrome(s: str) -> bool:
    cleaned = ''.join(char.lower() for char in s if char.isalnum())
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    return True

class TestPalindromeCheck(unittest.TestCase):
    def test_valid_palindrome(self):
        """Test a valid palindrome with mixed characters."""
        self.assertTrue(isPalindrome("A man, a plan, a canal: Panama"))

    def test_invalid_palindrome(self):
        """Test a string that is not a palindrome."""
        self.assertFalse(isPalindrome("race a car"))

    def test_empty_string(self):
        """Test an empty string, which is a palindrome."""
        self.assertTrue(isPalindrome(""))

    def test_single_character(self):
        """Test a single character, which is a palindrome."""
        self.assertTrue(isPalindrome("a"))

    def test_only_non_alphanumeric(self):
        """Test a string with only non-alphanumeric characters."""
        self.assertTrue(isPalindrome(".,!?"))

    def test_numbers_and_letters(self):
        """Test a palindrome with numbers and letters."""
        self.assertTrue(isPalindrome("12321a12321"))

    def test_case_sensitivity(self):
        """Test a palindrome with mixed case letters."""
        self.assertTrue(isPalindrome("RaCeCaR"))

    def test_spaces_only(self):
        """Test a string with only spaces."""
        self.assertTrue(isPalindrome("   "))

if __name__ == '__main__':
    unittest.main()

These test cases cover:

• Valid palindromes with punctuation and spaces
• Invalid palindromes
• Edge cases like empty strings and single characters
• Strings with only non-alphanumeric characters
• Mixed alphanumeric content
• Case sensitivity
• Strings with only spaces

Running the tests ensures the function handles all scenarios correctly, increasing confidence in its reliability.

Conclusion

Checking if a string is a palindrome while ignoring non-alphanumeric characters is a common coding problem that tests string manipulation and two-pointer techniques. The solution is efficient, with a time complexity of O(n) and space complexity of O(n) for the cleaned string. By incorporating comprehensive unit tests, we can verify the function’s correctness across various cases. Mastering this algorithm equips you to tackle similar string-based problems with confidence.