125_Valid Palindrome

[easy] [string, two pointers]

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama"is a palindrome. "race a car"isnota palindrome.

Note: Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Solution 1: Two Pointers

Idea:

• Two pointer: one loop forward, one loop backward.

• Use function string.isalnum() to check if the character is alphanumeric.

Time Complexity: $O(n)$

Space Complexity: $O(1)$

def isPalindrome(s):
    """
    :type s: str
    :rtype: bool
    """
    # convert to lowercase
    s = s.lower()
    # two pointers
    left = 0
    right = len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left] != s[right]:
            return False
        else:
            left += 1
            right -= 1
    return True

Solution 2: Recursive

Idea:

• Handle from outside to inside. Use the same function recursively.

Time Complexity: $O(n)$

Space Complexity: $O(1)$

def isPalindrome(s):
    """
    :type s: str
    :rtype: bool
    """
    if len(s) < 2:
        return True

    if not s[0].isalnum():
        return isPalindrome(s[1:])
    elif not s[-1].isalnum():
        return isPalindrome(s[:-1])
    elif s[0].lower() != s[-1].lower():
        return False
    else:
        return isPalindrome(s[1:-1])