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