A palindrome is a word, number, phrase or other sequence of characters that reads the same forwards as it does backwards.

Some examples of a numeric palindrome are 777 or 12321. A palindrome can be a date such as 02-02-2020 or a time like 12:21.

I decided to create several methods to test for a palindrome and see which method was the best. For a deeper explanation of each of the methods and how they perorm visit

the GitHub Repo

Problem

Given a string s, determine if it is a palindrome.

There are a number of ways you can do this. The specifics depend on the language and on what the purposes of the exercise is. Are you just looking for the simplest algorithm, or are you looking to do a deeper inspection into how you can solve the problem?

Don't do what I do. Don't over think the problem and get it completely wrong. :)

Solution 1: Comparing individual characters.

Since the input is a string, I can easily compare individual characters of the string in most languages by using an index.

This solution will simply inspect each set of characters to determine if they match each other. If at any time a set of characters does not match it is immediately determined that the string is not a palindrome.

Algorithm: Loop

1. Get the length of the string
2. Set a start_index to 0 (A zero based index is presumed)
3. Set end_index to string_length - 1 (To account for zero based indexes)
4. While the start_index is less than the end_index repeat a loop.
5. If the character at start_index does not equal the character at end_index, return false.
6. Increment the start_index by 1.
7. Decrement the end_index by 1.
8. Evaluate loop
9. If loop ends, return true.

Implementation: Loop

public static bool IsPalindrome(string s)
{
    int start_index = 0;
    int end_index = s.Length - 1;

    while(start_index < end_index)
    {
        if(s[start_index] != s[end_index])
            return false;

        start_index++;
        end_index--;
    }
    return true;
}

Solution #2: The easy way

The straight forward method for determining if a string is a palindrome is to compare the string to the reverse of the string. If the reverse of the string matches the original string then it is a palindrome.

Algorithm: Linq

1. Reverse the string using the Linq Reverse() method
2. Convert the result of Reverse() to an array. (Reverse returns an enumerable)
3. Create a new string to represent the newly reversed string
4. If the reversed string is equal to the original string, return true, else false

Implementation: Linq

public static bool IsPalindrome(string s)
{
    return s.Equals(new string(s.Reverse().ToArray()));
}

Solution 3: Recursion

Recursion is often used to break a problem down into a smaller unit to simplify the test. Testing for a palindrome can also be done using recursion. This is similar to using a loop with two indexes to test. Instead of tracking an index the string is tested by sending a substring to be tested using the same method.

Algorithm: Recursion

1. If the string is less than or equal to a length of 1, then return true
2. If the first character is not equal to the last character, return false
3. Test if the substring without the first and last character is a palindrome

Implementation: Recursion

public static bool IsPalindrome_WithRecursion(string s)
{
    // A string of length 0 or 1, then it is a palindrome.
    if(s.Length <= 1)
        return true;

    if(s[0] != s[s.Length -1])
        return false;

    return IsPalindrome_WithRecursion(s.Substring(1, s.Length - 2));
}

Solution 4: Rube Goldberg

This method takes an approach that is more complicated than necessary. To see why I chose the name of the solution see Rube Goldberg machine.

Algorithm: Rube Goldberg

1. Get the midpoint of the string, accounting for an odd or even length string.
2. Get the last half of the original string as a substring that should be tested for equality with the first half of the string.
3. Reverse the second half of the string.
4. Test if the first half of the string is equal to the reversed half of the second string.

Implementation: Rube Goldberg

public static bool IsPalindrome_RubeGoldberg(string s)
{
    int midpoint = (s.Length%2 == 0) ? s.Length/2 : s.Length/2 + 1;

    // Split the string into two parts.
    var mirror = s.Substring(midpoint).ToCharArray(); // Take the second part of the string.

    // Reverse the second part, but since String class does not have a reverse method, use Array.
    Array.Reverse(mirror);

    // See if the two parts match.
    return s.Substring(0, s.Length/2).Equals(new String(mirror));
}

Summary

I was surprised how how some of these solutions performed. Two of the method were clearly less optimized that the other two. The top two solutions were fairly close to each other in how they performed. However, one solution was clearly the better method to use.