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\$
  • 1
    \$\begingroup\$ isPalindromeIterative("override"): true. \$\endgroup\$ – greybeard Feb 10 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\$ – Maarten Bodewes Feb 15 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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ "production strength" implementations without instance data should be singletons. \$\endgroup\$ – greybeard Feb 11 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\$ – Maarten Bodewes Feb 11 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 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Why did someone put a downvote (and its not -1)? I thought the purpose of the code review is to help people. \$\endgroup\$ – PacificNW_Lover Feb 10 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 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.