AlgoDaily 05: Validate Palindrome

“Given a string str, can you write a method that will return True if is a palindrome and False if it is not? If you’ll recall, a palindrome is defined as “a word, phrase, or sequence that reads the same backward as forward”. For now, assume that we will not have input strings that contain special characters or spaces, so the following examples hold:”

let str = 'thisisnotapalindrome';
isPalindrome(str);
// false

str = 'racecar';
isPalindrome(str);
// true

“For an extra challenge, try to ignore non-alphanumerical characters. The final solution that we present will handle all edge cases.”

This seems to call for a stack-based approach:

function isPalindrome(str) {
	if (str.length === 1) {
		return true;
	}
	str = str.toLowerCase().replace(/[^a-z0-9]+/g, '');
	let stack = [];
	let mid = Math.floor(str.length / 2);
	for (let i = 0; i < mid; i++) {
		stack.push(str[i]);
	}
	if (str.length % 2 !== 0) {
		mid += 1;
	}
	for (let i = mid; i < str.length; i++) {
		if (str[i] !== stack.pop()) {
			return false;
		}
	}
	return true;
}

The idea is to go to the mid-point of the string pushing each character on to the stack, then go through the second half of the string comparing each character to the top of the stack.

Flooring the mid-point handles strings with even and odd lengths. With an even length, it naturally ends up in the middle:

abc|def

With an odd length, it ends up one character before the mid-point character:

ab|cde

This then gets skipped by the mid += 1 for the second loop.

Test cases:

isPalindrome('thisisnotapalindrome');
// false

isPalindrome('racecar');
// true

isPalindrome('raccar');
// true

isPalindrome('A Santa Lived As a Devil At NASA');
// true

isPalindrome('gold');
// false

isPalindrome('a');
// true

Looking at Algo Daily‘s solution, it seems the above is more complicated then necessary. You can acually just reverse the string and see if it’s the same, having accounted for whitespace and other unwanted characters:

function isPalindrome(str) {
	if (str.length === 1) {
		return true;
	}
	str = str.toLowerCase().replace(/[^a-z0-9]+/g, '');
	return [...str].reverse().join('') === str;
}