125.Valid_Palindrome_(Easy).md

125. Valid Palindrome (Easy)

Link: https://leetcode.com/problems/valid-palindrome/

Question:

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"

Output: false

Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "

Output: true

Explanation: s is an empty string "" after removing non-alphanumeric characters.

Since an empty string reads the same forward and backward, it is a palindrome.

Two Pointers Solution:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Make s to be all lower case
        # use two pointers to compare
        # Increment l or decrement r if current elem is non-alphanumeric
        # when s[l] != s[r], return False

        # TC: O(n), SC: O(1)
        s = s.lower()
        l, r = 0, len(s)-1
        while l < r:
            # Increment l ptr if current s[l] is non-alphanumeric
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

Time Complexity: $O(n)$
Space Complexity: $O(1)$

Alternative Solution:

This solution requires you to handwrite a isalnum() function, which checks whether the given element is within the ASCII code A to Z or a to z or 0 to 9. Then use two pointer method to compare if the two elements are first alphanumeric, then convert them to lower case and compare if they are the same. While the left ptr or right ptr is not alphanumeric, we increment or decrement the left/right ptr to the element that is alphanumeric.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # ord() converts char into ASCII
        def is_alnum(self, i):
            return (ord('A') <= ord(i) <= ord('Z') or
                    ord('a') <= ord(i) <= ord('z') or
                    ord('0') <= ord(i) <= ord('9'))

        left, right = 0, len(s)-1
        while left < right:
            # Make sure left ptr does not increment out of bound
            while left < right and not is_alnum(self, s[left]):
                left += 1
            while left < right and not is_alnum(self, s[right]):
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True

Time Complexity: $O(n)$
Space Complexity: $O(1)$, because we don't need to create a newStr like the previous solution.

My Solution:

isalnum() to check if a letter is alphanumeric or not. Use lower() to convert char into lower case. [::-1] to reverse a string.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        newStr = ""
        for i in s:
            if i.isalnum():
                newStr += i.lower()
        return newStr == newStr[::-1]

Time Complexity: $O(n)$
Space Complexity: $O(n)$