LeetCode 125. Valid Palindrome – Python

October 20, 2024

What is the problem

Let’s start from simple thought process, and then build the understanding step by step. The challenge is to transform the string so that all the non-alphanumeric characters are not processed while solving the problem, comparison of characters in lowercase, and then check if the processed string is a valid palindrome or not.

Naive Solution

We can create a temporary string (Space Complexity: O(N)) where we only copy the alpha numeric characters from the original string and make them lowercase. After that we reverse the string and compare with original to see if both are equal.

def isPalindrome(s: str) -> bool:
    """
    naive solution
    Time Complexity - TC: O(N)
    Space Complexity - SC: O(N)    
    """
    # copy array and remove non alpha numeric
    # TC: O(N)
    # SC: O(N)
    new_str:str = ''.join([x.lower() for x in s if x.isalnum()])
    
    # reverse the array using slicing 
    # TC: O(N)
    # SC: O(N)
    reversed_str: str = new_str[::-1]

    return new_str == reversed_str
    
if __name__ == "__main__":
    print(isPalindrome("race a car")) # False

Optimized Solution

We can see in the above solution that we are iterating two times over the string. One for removing the non alpha numeric, lowercasing the characters. Second for reversing the string. And we are consuming extra memory as well for storing transformed string and the reversed string. So the challenge is how we come iterate over the string once and try to keep memory consumption as low as possible. One technique that comes to mind is Two-Pointers Pattern.



def isPalindrome(s: str) -> bool:
    """
    optimized solution - two pointer
    Time Complexity - TC: O(N)
    Space Complexity - SC: O(1)    
    """
    # two pointers
    left = 0
    right = len(s) - 1
    
    while left < right:
        
        # jump forward to alphanumeric character from left side
        while left < right and not s[left].isalnum():
            left += 1
            
        # jump backward to alphanumeric character from right side
        while left < right and not s[right].isalnum():
            right -= 1
        
        # here we check if palindrome criteria is going on successful
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1

    return True
            
if __name__ == "__main__":
    print(isPalindrome("race a car")) # False

Youtube

Talha Gillani