Code Puzzle: Palindrome Detector

The palindrome problem is a fun little programming exercise. Given a string, how can you determine that it is a palindrome (the same whether spelled forwards or backwards)?

There are a few solutions that come to mind.

  • loop solution: check each character against the character at the mirror position at the “other end” of the string
  • recursive solution: compare the first and last characters of the string, and pass the rest of the string into the same method, returning true until the comparison fails
  • reversal solution: reverse the string and compare the entire reversed version with the original. For a more performant variation, reverse the second half of the original and compare it with the first half.
  • hash solution: reverse the second half of the original string and compare its hash with the hash of the first half. Mathematically this can produce false positives but not false negatives, so maybe this is more accurate to call a non-palindrome detector. It’s probably not the best solution, but still a creative idea.

The first (available on github) is what I think of as the default palindrome detector. Essentially you just loop over the string, checking each character as you move from the beginning/end of the string to the center of the string.

public boolean isPalindrome(String input) {

   // only need to loop over half of the string because second half is checked at the same time as the first
   // also can break if you detect it's not a palindrome in which case don't need to check the rest
   int halfLength = input.length()/2;
   for(int i=0; i < halfLength; i++) {
      if(input.charAt(i) != input.charAt(input.length()-1-i)) {
         return false;
      }
   }
   return true;
}

The second one (also available on github) is a nice little example of a recursive algorithm. One issue with it is that String.substring() returns a new String, so you could quickly run out of memory if the String is very large. One way around that is for the method to pass the original String in the recursive calls so no new memory is allocated, and instead recurse on the indices you’re checking.

public boolean isPalindrome(String input) {

   // base case for recursion:
   // length 1 for odd-length starting strings, length 0 for even-length starting strings
   if(input.length() == 1 || input.isEmpty()) {
      return true;
   }

   if(input.charAt(0) == input.charAt(input.length()-1)) {
      return isPalindrome(input.substring(1,input.length()-1));
   }

   return false;
}

Finally, of course we would want to unit test all of this. Parameterized tests fit the bill quite well for something like this.

The fun with Palindromes doesn’t end here. We could ask other questions like “What if the string was in a 3GB file and we couldn’t load the whole thing into memory?” This question is left as an exercise for the reader or for a future blog post 🙂

What other variations on the palindrome problem can we ask? Can you think of other solutions?

Advertisements

Leave a comment

Filed under Software Engineering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s