3
\$\begingroup\$

I wonder if there could be a faster palindrome checker in Java. The best one I have is O(n/2) which is O(n) eventually:

  public static boolean isPalindromeNaive(String s) {
        StringBuilder sb = new StringBuilder(s);
        StringBuilder sbReverse = sb.reverse();

        if (s.equals(String.valueOf(sbReverse))){
            return true;
        }
        return false;
    }

    public static boolean isPalindromLessNaive(String s) {
        if (s.length()%2==0) {
            for (int i = 0; i<(s.length()/2); i++) {
                if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                    return false;
                }
            }
        }
        else {

            for (int i=0; i<(s.length()/2); i++) {
                if (s.charAt(i)!=s.charAt(s.length()-1-i)) {
                    return false;
                }

            }

        }

        return true;
    }

Also am I correct that my naive method is slower than less naive method? what is the time complexity of StringBuilder reverse() method? // suggestion for code design/pattern(s) are really welcomed!

\$\endgroup\$
4
\$\begingroup\$

A palindrome checker has to have a worst case of \$O(n)\$ because you have to check each character to verify that it is a palindrome.

I would expect your first solution to be slower than your second solution, as it checks each character twice. Unless your compiler's optimization is really brilliant, this should be slower. But the proof's in the pudding. If you really want to know, test it on a million strings and see. Analysis is great but testing is better.

        if (s.length()%2==0) {
            for (int i = 0; i<(s.length()/2); i++) {
                if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                    return false;
                }
            }
        }
        else {

            for (int i=0; i<(s.length()/2); i++) {
                if (s.charAt(i)!=s.charAt(s.length()-1-i)) {
                    return false;
                }

            }

        }

You notice anything about the two loops? They're identical. You can just do one loop with no outer if/else:

        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }

This works because you start from the ends and work your way to the middle. It will also work if you say i <= j (which checks the middle character if there is one), but that's not necessary. The middle character will always equal itself. You don't need to check it.

The thing that I don't like about s.length()-1-i is that it puts the burden on the compiler to realize that s.length() - 1 is constant relative to the loop. Also, it's conceivable that decrement is faster than subtraction in some implementations. Doing it this way means that we know that s.length() - 1 would only be calculated once. The other way we're relying on the compiler to optimize it.

I don't know how the StringBuilder reverse is implemented, but it's possible to implement it without changing the underlying data at all. Just index in the opposite direction. Even if they do copy it to a new structure, that can be done in \$O(n)\$ time. The comparison is also \$O(n)\$, so asymptotically that doesn't matter.

\$\endgroup\$
  • \$\begingroup\$ for (int i = 0, j = s.length() - 1; i < j; i++, j--) { if (s.charAt(i) != s.charAt(j)) { return false; } } very nice loop thanks \$\endgroup\$ – Mona Jalal May 26 '16 at 3:37
  • \$\begingroup\$ is there a special name to this kind of for loop? for example we say "Advanced for loop" to for (Integer i : allints) \$\endgroup\$ – Mona Jalal May 26 '16 at 3:55
  • 1
    \$\begingroup\$ @MonaJalal I guess that's called a foreach loop (in C# at least, I think its the same in Java). \$\endgroup\$ – EvilTak May 26 '16 at 5:35
  • \$\begingroup\$ I think the other name of advanced for loop is foreach loop @EvilTak \$\endgroup\$ – Mona Jalal May 26 '16 at 6:05
  • \$\begingroup\$ I don't know of a special name for this kind of loop. The only part that I'd find advanced is the use of commas to allow two variables in the declaration and update sections. Other than that, this is a standard for loop. \$\endgroup\$ – mdfst13 May 26 '16 at 8:51

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.