Recursive Function : Check for palindrome in Java

Question

I have a class that checks whether a string is a palindrome or not. I have two questions.

1) Is this the most efficient way to check for palindrome? 2) Can this be implemented recursively?

public class Words {

    public static boolean isPalindrome(String word) {
    String pal = null;
    word = word.replace(" ", "");
    pal = new StringBuffer(word).reverse().toString();
    if (word.compareTo(pal) == 0) {
        return true;
    } else {
        return false;
    }

    }

}

Have a test class to test this... Doubt its needed but here it is anyways if anyone cares to try it out to be able to help me with any of the two questions above...

public class testWords {

    public static void main(String[] args) {
    if (Words.isPalindrome("a") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("cat") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("w o    w") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("   a  ") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("mom!") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }

    }

}

thanks in advance for any help and or input :)

Answer 1

To implement a 'palindrome check' recursively, you must compare if the first and last characters are the same. If they are not the same the string is most certainly not a palindrome. If they are the same the string might be a palindrome, you need to compare the 2nd character with the 2nd to last character, and so on until you have strictly less then 2 characters remaining to be checked in your string.

A recursive algorithm would look like this:

public static boolean isPalindrome(String word) {
  //Strip out non-alphanumeric characters from string
  String cleanWord = word.replaceAll("[^a-zA-Z0-9]","");
  //Check for palindrome quality recursively
  return checkPalindrome(cleanWord);
}
private static boolean checkPalindrome(String word) {
  if(word.length() < 2) { return true;  }
  char first  = word.charAt(0);
  char last   = word.charAt(word.length()-1);
  if(  first != last  ) { return false; }
  else { return checkPalindrome(word.substring(1,word.length()-1)); }
}

• Note, that my recursion method is not most efficient approach, but simple to understand

• Marimuthu Madasamy has a more efficient recursive method, but is harder to understand

• Joe F has listed an equivalently efficient iterative method
  which is the best approach for implementation because it cannot cause a stack overflow error

Answer 2

Here is another recursive solution but using array which could give you some performance advantage over string in recursive calls (avoiding substring or charAt).

private static boolean isPalindrome(final char[] chars, final int from,
        final int to) {
    if (from > to) return true;
    return chars[from] != chars[to] ? false 
                                    : isPalindrome(chars, from + 1, to - 1);
}

public static boolean isPalindrome(final String s) {
    return isPalindrome(s.toCharArray(), 0, s.length() - 1);
}

The idea is that we keep track of two positions in the array, one at the beginning and another at the end and we keep moving the positions towards the center.

When the positions overlap and pass, we are done comparing all the characters and all the characters so far have matched; the string is palindrome.

At each pass, we compare the characters and if they don't match then the string is not palindrome otherwise move the positions closer.