How Do You Check for Palindromes?

A palindrome reads the same forwards and backwards once you settle what counts as a character. The usual definition for a phrase ignores case, spaces and punctuation.

def is_palindrome(text):
    cleaned = [char.lower() for char in text if char.isalnum()]
    return cleaned == cleaned[::-1]


print(is_palindrome("A man, a plan, a canal: Panama"))   # True
print(is_palindrome("hello"))                         # False
print(is_palindrome("No lemon, no melon"))             # True

The function does three things: it keeps only alphanumeric characters, it lowercases them so the comparison is case-insensitive, and it compares the cleaned list with its reverse.

Two details worth explaining. The isalnum test is what removes punctuation and spaces, and it is Unicode-aware, so accented letters are kept rather than stripped. And the comparison uses a list rather than the original string, because once you have removed the punctuation the sequence of characters is what matters, not the spacing.

There is a faster variant that avoids building the reversed copy: walk two pointers from each end of the cleaned list towards the middle and compare as you go. It does the same amount of work asymptotically but uses constant extra space, which matters only if the input is very large.

The one-line version people sometimes give, comparing text with text[::-1], is only correct if you do not need to ignore anything. It also fails on the empty string in some naive implementations, because the empty string is trivially a palindrome and the check has to handle that case deliberately rather than by accident.

Comparing text with text[::-1] tells you whether the exact characters are symmetric. It does not tell you whether the text is a palindrome in the sense people mean, because a phrase like A man, a plan, a canal: Panama is a palindrome once case and punctuation are ignored, and the raw comparison says it is not.

The fix is to normalise first, and normalisation has to happen before the comparison. There are two reasonable normalisations. The common one keeps only letters and digits and lowercases them, which handles punctuation, spaces and case. The stricter one is to keep only letters, which is what most published definitions use, and it treats A string with a 3 inside it differently from one without.

On the complexity question, the naive comparison of text with text[::-1] is O(n) in time, so it is already linear. What people sometimes worry about is space, because building the reversed copy allocates a second string of the same length. The two-pointer version avoids that: clean the string once, then compare the character at position i with the character at position length minus one minus i, moving inwards until the pointers meet. That is still O(n) time but O(1) extra space beyond the cleaned copy.

For a string algorithm interview the two-pointer walk is usually the expected answer, because it shows you can reason about the problem rather than reaching for a one-liner. In Python the list comprehension version is perfectly acceptable and much shorter, and the honest thing to say is that the constant-factor difference matters far less than the correctness of the normalisation step.