LC 125 - 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.

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

Links

Question here and solution here

Solution

concept

We will use a two-pointer method to scan the word from the start and end, and we will check if the char are the same at the two places.

We can either first clear up the string and then use two-pointers, but this will have extra memory $O(n)$ A better way is to use two-pointers directly and this way the memory is $O(1)$.

code

class MySolution:
	"""
	clear up string first
	"""
    def isPalindrome(self, s: str) -> bool:
        alpha_str = ""
        for c in s:
            if c.isalnum():
                alpha_str += c.lower()

        i, j = 0, len(alpha_str) - 1
        while i < j:
            if alpha_str[i] != alpha_str[j]:
                return False
            i += 1
            j -= 1

        return True

class Solution:
	"""
	two pointer solutiokn
	O(1) memory
	O(n) time
	"""
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1

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

Complexity

time: $O(n)$
space: $O(1)$