Palindrome check in Javascript

25x faster than the standard answer

function isPalindrome(s,i) {
 return (i=i||0)<0||i>=s.length>>1||s[i]==s[s.length-1-i]&&isPalindrome(s,++i);
}

use like:

isPalindrome('racecar');

as it defines "i" itself

Fiddle: http://jsfiddle.net/namcx0yf/9/

This is ~25 times faster than the standard answer below.

function checkPalindrome(str) {
  return str == str.split('').reverse().join('');
}

Fiddle: http://jsfiddle.net/t0zfjfab/2/

View console for performance results.

Although the solution is difficult to read and maintain, I would recommend understanding it to demonstrate non-branching with recursion and bit shifting to impress your next interviewer.

explained

The || and && are used for control flow like "if" "else". If something left of || is true, it just exits with true. If something is false left of || it must continue. If something left of && is false, it exits as false, if something left of a && is true, it must continue. This is considered "non-branching" as it does not need if-else interupts, rather its just evaluated.

1. Used an initializer not requiring "i" to be defined as an argument. Assigns "i" to itself if defined, otherwise initialize to 0. Always is false so next OR condition is always evaluated.

(i = i || 0) < 0

2. Checks if "i" went half way but skips checking middle odd char. Bit shifted here is like division by 2 but to lowest even neighbor division by 2 result. If true then assumes palindrome since its already done. If false evaluates next OR condition.

i >= s.length >> 1

3. Compares from beginning char and end char according to "i" eventually to meet as neighbors or neighbor to middle char. If false exits and assumes NOT palindrome. If true continues on to next AND condition.

s[i] == s[s.length-1-i]

4. Calls itself again for recursion passing the original string as "s". Since "i" is defined for sure at this point, it is pre-incremented to continue checking the string's position. Returns boolean value indicating if palindrome.

isPalindrome(s,++i)

BUT...

A simple for loop is still about twice as fast as my fancy answer (aka KISS principle)

function fastestIsPalindrome(str) {
  var len = Math.floor(str.length / 2);
  for (var i = 0; i < len; i++)
    if (str[i] !== str[str.length - i - 1])
      return false;
  return true;
}

http://jsfiddle.net/6L953awz/1/


Maybe I will suggest alternative solution:

function checkPalindrom (str) {
  return str == str.split('').reverse().join('');
}

UPD. Keep in mind however that this is pretty much "cheating" approach, a demonstration of smart usage of language features, but not the most practical algorithm (time O(n), space O(n)). For real life application or coding interview you should definitely use loop solution. The one posted by Jason Sebring in this thread is both simple and efficient (time O(n), space O(1)).


The logic here is not quite correct, you need to check every letter to determine if the word is a palindrome. Currently, you print multiple times. What about doing something like:

function checkPalindrome(word) {    
    var l = word.length;
    for (var i = 0; i < l / 2; i++) {
        if (word.charAt(i) !== word.charAt(l - 1 - i)) {
            return false;
        }
    }
    return true;
}

if (checkPalindrome("1122332211")) {
    document.write("The word is a palindrome");
} else {
    document.write("The word is NOT a palindrome");
}

Which should print that it IS indeed a palindrome.

Tags:

Javascript