Palindrome algorithms: What’s fastest reverse vs. compare. 1

Today during a meeting a simple coding question came up as to how to write a palindrome function.  A palindrome is a word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction.^[1] 

Examples: mom , level, radar, tenet …

There are quite a few programmatic solutions to the problem, the interesting part was not the solution to the problem but which solution performed better.  The two solutions discussed (algorithms in question ) are below, coded in PHP.

Function 1 : Compare outside-in by letter :Begin at the ends and compare moving inward

// Function is_palidrome_compare($s) begins at the end of each string and compares the letters one by one until a mismatch
function is_palidrome_compare($s)
{
$len=strlen($s);
$midpoint=round($len/2);

$i=0;
while ( $i < $midpoint )
{
if ($s[$i]!=$s[$len-$i-1]) //no match return false
return false;
$i++;
}
return true; //if we get here then return true
}

Function 2 : Reverse and compare : Take in the initial string , reverse

it and compare

// Function is_palidrome_reverse simply reverse the string and does a compare
function is_palidrome_reverse($s)
{
$s1=strrev($s);
if ($s1==$s) //reverse string and compare
return true;
else
return false;
}

Now it became unclear during the conversation which method was faster, since it appeared that the reverse and compare may cause more iterations , was the reverse n iterations (Reversals per letter) + a compare or was the compare faster with length/2 comparisons, where at most half the letters would need to be compared.

I was not totally sure, so I figured the best thing would be to create a simple PHP page that tried both approaches and calculated their times, the resulting code is below.

PHP palindrome test results

You can run the palindrome test script  for yourself here..

Results for 100 time(s)

Function: FUNC_PALIDROME_REVERSE; Time: 1.9384186267853 secs.
Function: FUNC_PALIDROME_COMPARE; Time: 3.0043232440948 secs.

Based on several runs the string reverse method appears to be faster.  This is far from a definitive answer , since programming language, computer hardware, fine tuning either algorithm may result in a different result. But it typically is the case that loops or string reversal operations are faster than comparisons.

PHP Test file

TRy it for yourself:

•  Run Palindrome here:  directly.
• Download the palidromes text  file along with the code below and run it on a PHP server.

I used a palindrome.txt file to hold the palindromes and the php code uses this file , alternatively you can skip the file and comment in line 48 ( and comment our line 50) if you just want to use the test array.