Java Palindrome - Time & Space Complexity

Question

Which of these three methods is the most efficient?

Also, what is the time & space complexity of each?

public class Palindrome {

    public static boolean isStringBased(String word) {
        if (word == null || "".equals(word)) {
            return false;
        }
        String lowerCasedWord = word.toLowerCase();
        int i = 0;
        int j = lowerCasedWord.length() - 1;

        while (i < j) {
            if (lowerCasedWord.charAt(i) != lowerCasedWord.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }

    public static boolean isPalindromeRecursive(String input) {
        if(input.length() == 0 || input.length() == 1) {
            return true;
        }
        if(input.charAt(0) == input.charAt(input.length()-1)) {
            return isPalindromeRecursive(input.substring(1, input.length()-1));
        }
        return false;
    }

    public static boolean isPalindromeIterative(String input) {
        boolean retValue = false;
        int length = input.length();
        for( int i = 0; i < length/2; i++ ) {
            if (input.charAt(i) == input.charAt(length-i-1)) {
                retValue = true;
            }
        }
        return retValue;
    }
}

Answer 1

You present undocumented code
(yours, truly? StringBased looks different).

let me try and just code it more tersely, correcting the iterative variety:

/** check a <code>CharSequence</code> to be a <em>palindrome</em> */
static interface Palindrome {
    /** @return <code>true</code> if <code>word</code>
     *  is a <em>palindrome</em> else <code>false</code> */
    boolean isPalindrome(CharSequence word);

    static class StringBased implements Palindrome {
        public boolean isPalindrome(CharSequence word) {
            if (word == null || 0 == word.length())
                return false;
            String lowerCasedWord = word.toString().toLowerCase();
            for (int i = 0, j = word.length() - 1; i < j; i++, j--)
                if (lowerCasedWord.charAt(i) != lowerCasedWord.charAt(j))
                    return false;
            return true;
        }
    }
    static class Recursive implements Palindrome {
        public boolean isPalindrome(CharSequence input) {
            int last;
            return input.length() <= 1
                || input.charAt(0) == input.charAt(last = input.length()-1)
                   && isPalindrome(input.substring(1, last));
        }
    }
    static class Iterative implements Palindrome {
        public boolean isPalindrome(CharSequence input) {
            int length = input.length();
            for( int i = 0; i < length/2; i++ )
                if (input.charAt(i) != input.charAt(length-i-1))
                    return false;
            return true;
        }
    }
    public static void main(String[] args) {
        Palindrome[]checkers = {
                new StringBased(),
                new Recursive(),
                new Iterative()
            };
        String [] checks = { "", "a", "aa", "ab", "Aba", "abc", "aaba", };
        System.out.print('\t');
        for (String check: checks)
            System.out.print("\t\"" + check + '"');
        for (Palindrome checker: checkers) {
            System.out.print('\n' + checker.getClass().getSimpleName() + ":\t");
            for (String check: checks)
                System.out.print(checker.isPalindrome(check) + "\t");
        }
    }
}

StringBased still is different (Evitareti is isPalindromeIterative()):

              ""      "a"     "aa"    "ab"    "Aba"   "abc"   "aaba"
StringBased:  false   true    true    false   true    false   false   
Recursive:    true    true    true    false   false   false   false   
Iterative:    true    true    true    false   false   false   false   
Evitareti:    false   false   true    false   false   false   true    

StringBased and Recursive use O(n) additional space.
With respect to time,

1. DON'T assume: model & measure
   (using a framework, microbenchmarking where appropriate (e.g. here))
2. your mileage will vary

Answer 2

First solution requires O(1) space and O(n) complexity.

The last one looks to be less than 100% efficient, because you could directly return false when you find out it is not a palindrome, but it continues until the loop ends.