Need help with palindrome recurse method in Java

Question

I've seen the other recursive palindrome questions and I've seen the answers, but the one I have is a little different. It needs to be able to check a string with spaces and punctuation and ignore them (I know, they technically aren't palindromes), so strings such as "Madam, I'm Adam" should return true, but my program is not. Here's what I have:

public static boolean isPalindrom(String s){
        System.out.println(s);
        if (!Character.isLetter(s.charAt(0))){
            isPalindrom(s.substring(1,s.length()));
        }
         if (!Character.isLetter(s.charAt(s.length()-1))){
            isPalindrom(s.substring(0,s.length()-1));
        }
         if (s.length() == 1){

            return true;
        }
         if (s.length() == 2){
            if (s.substring(0,1).equalsIgnoreCase(s.substring(s.length()-1))){

                return true;
            }
            else
                return false;
        }
        if (!(s.substring(0,1).equalsIgnoreCase(s.substring(s.length()-1)))){

            return false;
        }

            return isPalindrom(s.substring(1,s.length()-1));

    }

The problem is that once it starts unwinding the recursion, the strings that contained the spaces and punctuations start returning false. I'm not sure what to do. I've been messing around trying different solutions for about an hour now.

p.s. I'm trying not to use regular expressions to remove the spaces and punctuation and such.

Answer 1

A non-recursive method that runs under or at O(n/2) in the worst-case (full search). This is more performant when the String is a LONG one... Here's the implementation...

class PalindromeClass {

    /**
     * This method will run under or at O(n/2) with n = sentence.size()
     * @param sentence is a given String sentence.
     * @return true if the given sentence is a palindrome.
     */
    public static boolean isPalindrome(String sentence) {
        sentence = sentence.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
        char[] sentenceChars = sentence.toCharArray();
        for (int i = 0; i < sentenceChars.length / 2; i++) {
            if (sentenceChars[i] != sentenceChars[sentenceChars.length - 1 - i]) {
                return false;
            }
        }
        return true;
    }

Running this with short, long and with wrong parameters give you the correct values...

public static void main(String[] args) {

String wrong = "ABCA";
System.out.println("Is '" + wrong + "' a palindrome? ");
System.out.println(isPalindrome(wrong));

String none = "A'";
System.out.println("Is '" + none + "' a palindrome? ");
System.out.print(isPalindrome(none));

String a = "Madam, I'm Adam";
System.out.println("Is '" + a + "' a palindrome? ");
System.out.println(isPalindrome(a));

String b = "abba";
System.out.println("Is '" + b + "' a palindrome? ");
System.out.println(isPalindrome(b));

String toyota = "A Toyota. Race fast, safe car. A Toyota.";
System.out.println("Is '" + toyota + "' a palindrome? ");
System.out.println(isPalindrome(toyota));

String longestPalindrome = "Do good? I? No! Evil anon I deliver. I maim " +
    "nine more hero-men in Saginaw, sanitary sword a-tuck, Carol, I -- lo! " +
    "-- rack, cut a drowsy rat in Aswan. I gas nine more hero-men in Miami. " +
    "Reviled, I (Nona) live on. I do, O God!";
System.out.println("Is '" + longestPalindrome + "' a palindrome? ");
System.out.println(isPalindrome(longestPalindrome));
}

}

Here's the output of the execution...

Is 'ABCA' a palindrome? false
Is 'a' a palindrome? true
Is 'Madam, I'm Adam a palindrome?' true
Is 'abba a palindrome? true'
Is 'A Toyota. Race fast, safe car. A Toyota.' a palindrome? true
Is 'Do good? I? No! Evil anon I deliver. I maim nine more hero-men in Saginaw, sanitary sword a-tuck, Carol, I -- lo! -- rack, cut a drowsy rat in Aswan. I gas nine more hero-men in Miami. Reviled, I (Nona) live on. I do, O God!' a palindrome? true

Answer 2

When you get to one, you just have to move forward with it. like so. I leave it to you to fill in the blanks (special cases, lastNonIgnoredChar, etc)

char[] ignored = new char[] { ',' , ' ', '.'};

int firstNonIgnoredChar(String s) {
    for(int i = 0; i < s.length(); i++) {
        boolean found = false;
        for(char c : ignored) {
            if( c == s.charAt(i) ) found = true;
        }
        if(!found) return i;
    }
    return -1; // no good characters
}

boolean isPal(String s) {
    int first = firstNonIgnoredChar(s);
    int last = lastNonIngoredChar(s);

    if(s.length() == 0) return true;
    if(s.length() == 1) return true;

    return first < last
        && s.charAt(first) == s.charAt(last)
        && isPal(s.substring(first + 1, last - 1);
}

Answer 3

You don't return the result of the first two isPalindrom (which check for the cases started failing now...):

  if (!Character.isLetter(s.charAt(0))){
        return isPalindrom(s.substring(1,s.length()));
    }
     if (!Character.isLetter(s.charAt(s.length()-1))){
        return isPalindrom(s.substring(0,s.length()-1));
    }