Java - Word palindrome for LONG strings

Question

So, I'm doing this challenge called valid palindrome and I'm stuck.

My code works for small/medium strings but when it runs I get a Time Limit Exceeded message which means there has to be a better way to optimize my code.

I was looking at using the charAt() and do something like ... since it's a palindrome... split it half and do a quick check of opposing characters in a for loop but I'm stuck here.

/**
 *  Palindrome Word Checker
 *  Tests to see if an input phrase is a
 *  palindrome (read the same if read backward and forwards)
 */

import java.util.Scanner;

public class wordPalindrome {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System. in );
        System.out.println("Palindrome Word Checker\nEnter a phrase, please:");

        String theWord = "";

        while (true) {
            theWord = scanner.nextLine();
            System.out.println(theWord + ": " + wordPalindrome(theWord));
        }
    }
    public static boolean wordPalindrome(String word) {

        // SECONDLY, we check to see how we much of the word
        // is left until verification. We check first to prevent
        //  array (out of bounds) exception errors.


        if (word.length() == 0 || word.length() == 1) return true;

        // FIRST we take the last letter and compare it to the first letter
        // if it matches, then we move onward and return to the function
        // with a new word. By substring(), we take off the first/last letters
        // and we keep repeating this process until the length is
        // at 0 or 1 for odd/even lengthed words to verify its status
        if (word.charAt(word.length() - 1) == word.charAt(0))
            return wordPalindrome(word.substring(1, word.length() - 1));

        // if we fail to make an ID, then it's obviously
        // not a palindrome and we return false
        return false;
    }
}

Here is what "string" they use to crash my program: pastebin. How do I withstand a string that long? I can't obviously use String since it's so long... too much info.

Answer 1

A better way than recursion would be an iterative process. You can use charAt and a loop that processes half the string and the other half at the same time. I won't code it up, but I'll ive pseudocode that you could try to use. I recommend coding it up in Java as a challenge to yourself:

1. Determine length of the string
2. Initialize counter (i) to 0.
3. While i is less than length minus i, repeat the following:
   1. If the i'th character is not equal to (length-i)th character, return false immediately.
4. Once loop ends, return true (since no failures were found).