125. Valid Palindrome

easy two-pointers

Check if a string is a palindrome ignoring non-alphanumeric characters.

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

Approach

Use two pointers from both ends, skipping non-alphanumeric characters — O(n) time, O(1) space.

Solutions

Ruby

def is_palindrome(s)
  left, right = 0, s.length - 1
  while left < right
    left += 1 while left < right && s[left].match?(/[^a-zA-Z0-9]/)
    right -= 1 while left < right && s[right].match?(/[^a-zA-Z0-9]/)
    return false if s[left].downcase != s[right].downcase
    left += 1
    right -= 1
  end
  true
end

Python

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Go

func isPalindrome(s string) bool {
    left, right := 0, len(s)-1
    for left < right {
        for left < right && !isAlnum(rune(s[left])) {
            left++
        }
        for left < right && !isAlnum(rune(s[right])) {
            right--
        }
        if toLower(rune(s[left])) != toLower(rune(s[right])) {
            return false
        }
        left++
        right--
    }
    return true
}

func isAlnum(c rune) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
}

func toLower(c rune) rune {
    if c >= 'A' && c <= 'Z' {
        return c + 32
    }
    return c
}

TypeScript

function isPalindrome(s: string): boolean {
    let left = 0, right = s.length - 1;
    while (left < right) {
        while (left < right && !isAlnum(s[left])) left++;
        while (left < right && !isAlnum(s[right])) right--;
        if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
        left++;
        right--;
    }
    return true;
}

function isAlnum(c: string): boolean {
    return /[a-zA-Z0-9]/.test(c);
}

Elixir

defmodule Solution do
  def is_palindrome(s) do
    chars = s |> String.downcase() |> String.graphemes() |> Enum.filter(&alnum?/1)
    chars == Enum.reverse(chars)
  end

  defp alnum?(c), do: String.match?(c, ~r/^[a-z0-9]$/)
end