125. Valid Palindrome

Prompt

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.

Examples

• 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.

Solutions

Two Pointers Solution

In C++

bool isPalindrome(string s) {
	int l = 0; int r = s.size() - 1;
	while (l < r) {
		while (!isalnum(s[l]) && l < r) l++;
		while (!isalnum(s[r]) && l < r) r--;
		if (tolower(s[l]) != tolower(s[r])) return false;
		l++; r--;
	}
	return true;
}

Explanation

The idea here is to use Two Pointers, while also skipping nonvalid characters, so long as the pointers haven’t crossed. This solution is kind of similar to QuickSort’s Hoare Partitioning, as the two pointers work in a similar way.

Big O Analysis

Time Complexity

$O(n)$

Auxiliary Space Complexity

$O(1)$

Modern Functional Solution

In C++

bool isPalindrome(string s) {
	auto formatted = s 
		| views::filter([](char c){return isalnum(c);})
		| views::transform([](char c){return tolower(c);});
	return ranges::equal(formatted, formatted | views::reverse);
}

Explanation

When is the lowercased alphanumeric input string equal to its reverse?

Big O Analysis

Time Complexity

$O(n)$. We iterate through the string to filter and transform, and then again to compare.

Auxiliary Space Complexity

$O(1)$. C++20 views are Lazy adapters. No intermediate strings or containers are allocated