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;
 }
}

• greybeard: isPalindromeIterative("override"): true.
• Maarten Bodewes: What terrible programming practices are these? The functions are not named similarly, the checks on the input / word are different for each, unexplained and incorrectly implemented algorithms. Yuk.

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

• greybeard: "production strength" implementations without instance data should be singletons.
• Maarten Bodewes: Nice rewrite. What I'm missing here is the fact that Palindrome is not a verb. It should really be PalindromeChecker or something similar. Terse is fine, but removing the braces is not (this is subjective, but I guess if > 90% of devs agree on it, that you need to make it explicit in your answer that most don't agree).
• greybeard: (I learned coding with each line adding 2.5 grams to the program, and the quality of rubber bands important to the mental balance of a coder. PalindromeChecker was the name of the abstract class when I first typed this... (I tried renaming the predicate to is() when I shortened the interface name - didn't work for me.))

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.

• PacificNW_Lover: Why did someone put a downvote (and its not -1)? I thought the purpose of the code review is to help people.
• greybeard: (@PacificNW_Lover Up to this comment, nobody downvoted this answer. Your question has been down-voted once, with no up-vote. By rights, somebody found it not useful (as it was at the time of the vote).)