9. Valid Palindrome

#leetcode/125

Problem 🔗

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.

Solution

Solution in C++ using two pointers

The solution is very simple.

• If a character is not alphanumeric we can simply ignore it and update our pointer to the next character (for both pointers)
• If the two compared characters aren't equal, we can return false
• If the two compared characters are equal, we update both pointers and continue

Finally, after checking all characters, the string must be a valid palindrome so we can return true.

bool isPalindrome(string s) {
	for(int start = 0, end = s.size() - 1; start < end;) {
		/* If s[start] is a num we can drop it */
		if(!isalnum(s[start]))
			start++;
		/* If s[end] is a num we can drop it */
		else if(!isalnum(s[end]))
			end--;
		/* If the two compared characters aren't equal, return false */
		/* We don't need to care about doing tolower() on a number, it will return the same result for both number */
		else if(tolower(s[start]) != tolower(s[end]))
			return false;
		/* If the two compared characters are equal */
		else {
			start++;
			end--;
		}
	}
	return true;
}

• Time complexity: $O(n)$ (where n is the size of the string)
• Space complexity: $O(1)$