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;
}