Python Programming Challenge 26: Valid Palindrome

Today, we have a relatively easy challenge from Leetcode – The Valid Palindrome problem.

The Valid Palindrome Problem

This problem requires us to write a function called isPalindrome() that accepts a string s.

Considering only alphanumeric characters and ignoring cases, the function needs to determine whether the string is a palindrome.

A palindrome is a string that spells the same backward as forward. For instance, 'madam' is a palindrome as we get the same spelling whether we spell the word forward or backward.

In contrast, 'hello' is not a palindrome as it is spelt 'olleh' backwards.

Suggested Approach

To solve the Valid Palindrome problem, we can use two pointers – left and right.

At the beginning, left and right point to the first and last characters in the string respectively.

Now, we are ready to iterate over the string.

As we are instructed to only consider alphanumeric characters, we need to keep moving left and right inwards until they are both pointing at an alphanumeric character, or until left is no longer smaller than right.

When left and right are both pointing at an alphanumeric character, we compare the two characters and determine whether they are the same.

If they are not the same, the string is not a palindrome. Hence, we return False. On the other hand, if they are the same, we move left and right one unit inwards and repeat the steps above while left is smaller than right.

If we reach the stage where left is no longer smaller than right, we have iterated over all the characters in s and failed to find a case where left and right point at a different alphanumeric character.

This means s is a palindrome. Hence, we return True and the function is complete.

Graphical Illustration

Here’s a graphical illustration of how this approach works for the Valid Palindrome problem.

Suggested Solution

Here’s the suggested solution for the Valid Palindrome problem in Python:

def isPalindrome(s):
    left = 0
    right = len(s)-1

    while left < right:
        # Step 1
        while left < right and not s[left].isalnum():
            left += 1
        #Step 2
        while left < right and not s[right].isalnum():
            right -= 1

        # Steps 3 and 4
        if s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1

    # Step 6
    return True

Here, we first define a function called isPalindrome() with one parameter s.

Inside the function, we declare and initialize two variables called left and right and assign the indexes of the first and last characters in s to them.

Next, we use a while loop to iterate over s while left is smaller than right.

Inside the loop, we use two other while loops to update the values of left and right. We keep adjusting their values until they both point at an alphanumeric character. This corresponds to steps 1 and 2 in the suggested approach discussed above. We use the built-in isalnum() function to determine whether s[left] and s[right] are alphanumeric characters. If they are not, we update the values of left and right accordingly.

Once left and right both point to alphanumeric characters, we convert the characters to lowercase and compare if they are the same on line 14.

If they are not, s is not a palindrome. Hence, we return False on line 15.

Else, we update the values of left and right by incrementing and decrementing them by 1 respectively.

Finally, outside the while loop, when left is no longer smaller than right, we have finished iterating over all the characters in s. If we did not return False previously, s is a palindrome. Hence, we return True on line 21.

With that, the function is complete.