Palindromes

The other evening while I was watching TV, I happened to have my laptop out, so I started dabbling around in Firebug just for the heck of it. I'll often just start writing functions for no particular reason, other than to refresh my skills or perhaps discover something about Javascript that I hadn't previously known.

So I was monkeying around, and I decided to write a function to determine if a string were a palindrome. This is not a very difficult problem, but it might make for a descent introductory interview question (one of those questions you'd ask to rule out the truly inept).

With problems like this, I'm mostly interested in two things:

  1. Writing the function in a clever way, so as to achieve the least amount of code possible
  2. Writing the function in the most efficient way possible

Now, if it were Ruby, writing the clever solution (which might also happen to be the most efficient solution in that language -- not sure) would be ridiculously easy:

def pal(s)
   s == s.reverse
end

That's so trivial, it's probably not even worth writing.

But Javascript doesn't have a .reverse() method on strings, so you have to take an extra step (still pretty easy though):

function pal(s)
{
   return s === s.split('').reverse().join('');
}

Split the string into an array, reverse the array, and then join it back together. Since this is all native Javascript stuff, it turns out to be reasonably fast, though one might expect you could do better.

For grins and giggles, I decided to see how a manual solution, where I compare characters starting at each end of the string and work towards the middle, would compare:

function pal(s)
{
   var i, j,
   len = s.length,
   mid = Math.floor(len / 2);

   for (i = 0, j = len - 1; i < mid; i++, j--)
   {
      if (s.charAt(i) !== s.charAt(j)) return false;
   }
   return true;
}

This function will probably fail quickly, so that's good, but it also turns out to be generally faster than the split/reverse/join version. It makes sense, since you're going through the string only one time and twice as fast as normal since you're traversing from both ends at the same time.

Can you do even better though? Maybe. At least in Firefox you can, and quick tests seemed to confirm across other browsers too (but I didn't test extensively).

What if we split the string in half, and only reverse half of it. Then we can compare the first half with the original half:

function pal(s)
{
   var len = s.length,
   x = len / 2,
   y = x === Math.floor(x) ? x : (x = Math.floor(x)) + 1;

   return s.substr(0, x).split('').reverse().join('') === s.substr(y,len);
}

The idea here is just split the string in half, reverse one of the two pieces and compare them. For example:

TOOT: splits into "TO" and "OT." Reverse one of them, say the second part ("OT") and compare.

If you've got a odd number of characters, you can ignore the middle most character:

RACECAR: splits into "RAC" and "CAR" (ignore the "E" in the middle). Reverse the second part ("CAR") and compare.

As it turned out, this seemed to be faster than the other two methods. Not by orders of magnitude, but not insignificantly either. Here are the number from Firefox, running each function 10,000 time on the string "gohangasalamiimalasagnahog" (go hang a salami, i'm a lasagna hog).

  • (Traverse from both ends): 797ms
  • (Split/Reverse/Join): 969ms
  • (Compare halves): 640ms

Of course, numbers varied slightly during each run, but overall the they were consistent relative to each other.

So there ya go. Nothing in particular I wanted to point out here; just found it interesting and thought you might too.

Think my code sucks? Got a better solution? Say so in the comments (you won't hurt my feelings).

5 Responses

  1. Luan Nguyen Says:

    Yeah, your code sucks 🙂

    This is the fastest method:

    function pal(s)
    {
    var i, j,
    len = s.length,

    for (i = 0, j = len – 1; i < j; i++, j–)
    {
    if (s.charAt(i) !== s.charAt(j)) return false;
    }
    return true;
    }

  2. sstchur Says:

    The code, as you have it written, does not actually work in Javascript (but that appears to be just due to a typo, so I can forgive that).

    But so far as I can tell, your solution is conceptually the same as the second solution I outlined, albeit you did it with a bit less code, but it does not turn out to be faster than the "compare halves" version (at least, not in Javascript/Firefox).

  3. Ola Says:

    I find it weird that all that splitting, reversing and joining are faster in JavaScript as opposed to the compare halves method.

    Probably because implementation of those is in C and we are going through the array in JavaScript?

    Compare halves should be significantly faster in other languages.

  4. sstchur Says:

    Ola:

    That's one of the things I find most interesting about Javascript. Every time I think I know what is going to be fastest, I turn out to be wrong.

    I've found that unless you really know the internal working of the Javascript implementation in your particular browser (and I'm sure there are some people that do, but I am not one of them), then there simply is no substitute for trying out your algorithm to see if it performs as you expected.

    To be clear though, the splitting, joining and reversing wasn't faster in Javascript (did I somehow imply it was and not realize it?). The compare halves version was fastest in Javascript.

    Personally, I would have expected the traversal from both ends to have been fastest.

  5. Ola Says:

    I guess I should have looked at the actual times but this was what led me to believe it was faster…

    "As it turned out, this seemed to be faster than the other two methods."

    And yea, what you discovered is actually what I expected.

    The compare halves only has to go through half of the string while the traversal from both ends has to create an array, reverse it, change it back to a string and then compare the original string with the current string…

Got something to say?

Please note: Constructive criticism is welcome. Rude or vulgar comments however, are not and will be removed during moderation.