In continuation of this series, looking at the basics of coding and typical questions, we have today another classic of the software world: Palindromes.
a word, phrase, or sequence that reads the same backward as forward, e.g., madam or nurses run.
Today we are going to cover a number of methods for solving this small task. You can look here for a github link to a palindrome library in dotnet core with test units for each method. We are going to use the following methods, each valid, and some with more interesting uses.
General looping evaluation
Using array methods and Linq for evaluating
Using SequenceEqual, which is more commonly used for typically more indepth evaluation
Using a recursive method to evaluate the string
First Things First
We will only be covering US character set ASCII, due to the complexities of multi-language evaluation being outside of the scope of “Super Basics.” And we must assume that we are ignoring white spaces and punctuation for our phrases being evaluated.
In order to assist us in this process, we should first create a method that will help us remove all punctuation and white space from the phrase.
public static string StripPunctuationAndWhiteSpaceFromString(string phrase)
{
return new string (phrase.ToCharArray().Where(c => !char.IsPunctuation(c) && !char.IsWhiteSpace(c)).ToArray());
}
Here we are taking the phrase as in input and converting it to a character array. This is a native function of the string object that will allow use to use the character native function to evaluate each character individually to see if they are punctuation (comma, period, semicolon, etc.) or white space (space, return, non-breaking space). Using the Where evaluation of the System.Linq library, we will be able to return this string “sanitized” to our purposes. Separating this logic will help avoid mess in our code and keep it DRY (don’t repeat yourself).
Super Simple Answer
The most typical and simple answer to this problem is to loop over each character individually. Check if opposing characters on either side of the array match, and if we encounter a miss-match, return that the phrase isn’t a palindrome. Else we return that the phrase is a palindrome.
public static bool IsPalindromeWithForLoop(string phrase)
{
var phraseWithoutPunctuation = StripPunctuationAndWhiteSpaceFromString(phrase).ToLower();
int length = phraseWithoutPunctuation.Length;
int iterations = length / 2;
for (int i = 0; i < iterations; i++)
{
if (phraseWithoutPunctuation[i] != phraseWithoutPunctuation[length - i - 1])
return false;
}
return true;
}
Fairly descriptive, easy to read, and even a novice will not have to check for what an internal class may or may not be doing. While this is perfectly fine, it does not take advantage of other more terse ways of accomplishing the task.
Something More Substantial
With a small application of internal methods, like with the StripPunctuationAndWhiteSpaceFromString method, we can expand and accomplish the same task with two lines. One if you want to make a rather over wide line.
public static bool IsPalindromeWithArray(string phrase)
{
var phraseWithoutPunctuation = StripPunctuationAndWhiteSpaceFromString(phrase).ToLower();
return phraseWithoutPunctuation == new string (phraseWithoutPunctuation.Reverse().ToArray());
}
Here we have a simple use of the Reverse portion of Linq, converting to an array, and subsequently comparing it as a new string to the original content. This would be my typical application of the solution. Short, simple, and it is easily read.
Another Option
We can do the same sort of functionality with SequenceEqual, however this is more intended for doing a one layer deep comparison of an object and its properties. You can look at the documentation to see what i’m talking about in regards to this statement. Regardless you are able to accomplish a slightly shorter, and equally efficient method.
public static bool IsPalindromeWithSequenceEqual(string phrase)
{
var phraseWithoutPunctuation = StripPunctuationAndWhiteSpaceFromString(phrase).ToLower();
return phraseWithoutPunctuation.SequenceEqual(phraseWithoutPunctuation.Reverse());
}
A Taste of Black Magic
Recursion is a method that will continue to call itself onto the stack until it either runs out of stack space, or it completes its predefined termination and returns. This is a somewhat advanced methodology, and it comes from the world of mathematics more than from the world of software. There are many advantages that could be gained from using recursion, however as I lightly mentioned, you need to be cognizant of what your limited stack scope may be. Some systems will have more overhead, some less. If you make a solution that goes over your native limits, you will run into issues. There are ways to alleviate and overcome this depending on your language and environment. Due to these limitations, I tend to avoid using recursion. There are also issues with working with peers that are thoroughly adverse to recursion. I would avoid it personally, however there are some nifty things that you can do. Here’s an example, that would require calling the method differently than the previous methods, but it should read fairly simply.
public static bool IsPalindromeWithRecursion(int rightIndex, int leftIndex, char[] phrase)
{
if (rightIndex == leftIndex || rightIndex < leftIndex)
return true;
else if (phrase[rightIndex] == phrase[leftIndex])
return IsPalindromeWithRecursion(--rightIndex, ++leftIndex, phrase);
else
return false;
}
Here we can see that we have our termination initially checked, if our right hand character index is lower or equal to the right index (which you can simply use a rightIndex <= leftIndex) we will exit, assuming that we have reached this point without any conflicts. The next comparison checks to see if we have a match on the mirrored character and call back another instance of this method with a new index for both right and left shifted before the call. If we fail our validation, we have mismatched characters, and we do not have a palindrome. This can be very efficient if the first few compared characters are mismatched, saving some of the memory that would be used in the more typical answers provided above.
Final Thoughts
Personally I find the palindrome question to be much less interesting that FizzBuzz, primarily because you get far less thought experiments on this problem than FizzBuzz. You could, and I’m certain someone already has, write a book just covering the breadth of what FizzBuzz could entail.
My only parting thought is that all of these methods will return truthy in the case of an empty string. To me this is a bit of a dual state quandary. Is an empty string a palindrome? I’ll leave you to your thoughts in this regard.