0
\$\begingroup\$

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;
    }
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ isPalindromeIterative("override"): true. \$\endgroup\$
    – greybeard
    Feb 10 '20 at 22:46
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 15 '20 at 21:36
2
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ "production strength" implementations without instance data should be singletons. \$\endgroup\$
    – greybeard
    Feb 11 '20 at 0:18
  • \$\begingroup\$ 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). \$\endgroup\$ Feb 11 '20 at 14:41
  • \$\begingroup\$ (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.)) \$\endgroup\$
    – greybeard
    Feb 11 '20 at 18:11
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Why did someone put a downvote (and its not -1)? I thought the purpose of the code review is to help people. \$\endgroup\$ Feb 10 '20 at 22:29
  • \$\begingroup\$ (@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).) \$\endgroup\$
    – greybeard
    Feb 10 '20 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.