Faster palindrome checker in Java

Question

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!

Answer 1

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.