Valid Palindrome

Easy

The problem

A phrase is a palindrome if it reads the same forwards and backwards after you ignore everything that is not a letter or a digit, and ignore the difference between capital and small letters. Given a string s, return true if it is a palindrome, otherwise false.

Example 1
Input: s = "No lemon, no melon"
Output: true
After ignoring spaces, the comma and capitals, we get "nolemonnomelon", which reads the same both ways.
Example 2
Input: s = "hello, world"
Output: false
"helloworld" backwards is "dlrowolleh".
Example 3
Input: s = ". ,"
Output: true
Nothing is left after ignoring punctuation and spaces, and an empty text counts as a palindrome.

Limits

1 ≤ s.length ≤ 200,000
s contains printable ASCII characters (letters, digits, spaces, punctuation)

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A palindrome reads the same from both ends. What if you compare from the outside in?

The idea

Left and right pointers; skip anything that is not a letter or digit, compare lowercase characters, move inward.

Target: O(n) time, O(1) space

Go function shape

func isPalindrome(s string) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// IsPalindrome: ignoring case and non-alphanumerics, does it read the same both ways?
func IsPalindrome(s string) bool {
	alnum := func(c byte) bool {
		return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z'
	}
	lower := func(c byte) byte {
		if c >= 'A' && c <= 'Z' {
			return c + 32
		}
		return c
	}
	left, right := 0, len(s)-1
	for left < right {
		if !alnum(s[left]) {
			left++
		} else if !alnum(s[right]) {
			right--
		} else if lower(s[left]) != lower(s[right]) {
			return false
		} else {
			left++
			right--
		}
	}
	return true
}

Read the lesson: Two Pointers