Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0125 - Valid Palindrome
    0125 - Valid Palindrome
    0125 - Valid Palindrome
    0125 - Valid Palindrome

    0125 - Valid Palindrome

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/valid-palindrome/

    Solution 1 - Two Pointer Approach

    A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward. Use two pointers starting from opposite ends, skipping non-alphanumeric characters, and comparing lowercase versions of valid characters.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Filter and Reverse Compare

    Filter out all non-alphanumeric characters and convert to lowercase to build a cleaned string. Then compare the cleaned string to its reverse. If they are equal, the input is a palindrome.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0125.1 - Valid Palindrome - Solution 1 - Two Pointer Approach """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isPalindrome(self, s: str) -> bool:
        """Valid Palindrome Function"""
        l, r = 0, len(s) - 1

        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1

        return True


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isPalindrome("A man, a plan, a canal: Panama"))  # True
    print(Solution().isPalindrome("race a car"))                      # False
    print(Solution().isPalindrome(" "))                               # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0125.2 - Valid Palindrome - Solution 2 - Filter and Reverse Compare """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isPalindrome(self, s: str) -> bool:
        """Valid Palindrome Function"""
        cleaned = ''.join(c.lower() for c in s if c.isalnum())
        return cleaned == cleaned[::-1]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isPalindrome("A man, a plan, a canal: Panama"))  # True
    print(Solution().isPalindrome("race a car"))                      # False
    print(Solution().isPalindrome(" "))                               # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()