#10 Easy Time O(n) Space O(1) Animated

Valid Palindrome

A string is a palindrome if, after lowercasing and removing non-alphanumerics, it reads the same forwards and backwards.

LeetCode ↗

Approach: Two Pointers — In Place

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

A string is a palindrome if, after lowercasing and removing non-alphanumerics, it reads the same forwards and backwards.

Constraints

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

Solution — Two Pointers — In Place

O(n) O(1)

def isPalindrome(s):
    left, right = 0, len(s) - 1  # line 1
    while left < right:           # line 2
        while left < right and not s[left].isalnum():  # line 3
            left += 1              # line 4
        while left < right and not s[right].isalnum():  # line 5
            right -= 1             # line 6
        if s[left].lower() != s[right].lower():  # line 7
            return False           # line 8
        left += 1                  # line 9
        right -= 1                 # line 10
    return True                    # line 11

Two Sum II - Input Array Is Sorted

Valid Palindrome

Steps

Description

Constraints

Tags

Solution — Two Pointers — In Place