Efficient way to determine whether an input string is a palindrome or not

Question

I recently wrote this short method to determine whether a string is a palindrome. I was wondering what I could do to make it more efficient, surely I'm missing simple built-in functions that can speed up the calculation.

Thank you all for your help!

boolean checkPalindrome(String inputString) {

    ArrayList<Character> arrFront = new ArrayList<Character>();
    ArrayList<Character> arrBack = new ArrayList<Character>();

    for(int i=0; i<inputString.length()-1; i++) {
        arrFront.add(inputString.charAt(i));
    }

    for(int i=inputString.length()-1; i>0; i--) {
        arrBack.add(inputString.charAt(i));
    }

    StringBuilder builder1 = new StringBuilder(arrFront.size());
    for (Character c : arrFront) {
        builder1.append(c);
    }
    String front = builder1.toString();

    StringBuilder builder2 = new StringBuilder(arrBack.size());
    for (Character c : arrBack) {
        builder2.append(c);
    }
    String back = builder2.toString();

    return(front.equals(back));
}

what do you mean by `speed up`? time complexity, or less code? — ZhaoGang, Dec 24 '18 at 00:41
You mean like [this](https://stackoverflow.com/a/4139065/8534008)? Note that this is less code, but is [not very efficient](http://componentsprogramming.com/palindromes/) — GBlodgett, Dec 24 '18 at 00:43
I'm voting to close this question as off-topic because it belongs on Code Review SE. — Andrey Tyukin, Dec 24 '18 at 00:46
@AndreyTyukin Yes the simple loop solution (`for (int i = 0; i < n/2; ++i) { if (str.charAt(i) != str.charAt(n-i-1)) return false; }`) is a better choice if you're concerned about efficiency — GBlodgett, Dec 24 '18 at 00:50
@GBlodgett Making use of `str.length()` will also speed up things! Returning early will safe some time. — Glains, Dec 24 '18 at 01:03
@Glains That's what `n` represents in the code. It is resolved to a variable to avoid the `length()` method being called twice every iteration of the loop — GBlodgett, Dec 24 '18 at 01:05

score 5 · Answer 1 · answered Dec 24 '18 at 01:34

In terms of efficiency, it is not always about built-in functions and using libraries (although in many cases they are the best choice). But sometimes a simple loop like this could be the most simple and efficient way:

private boolean checkPalindrome(String inputString) {
    for(int i = 0, j = inputString.length() - 1; i < j; i++, j--) {
        if(inputString.charAt(i) != inputString.charAt(j)) {
            return false;
        }
    }
    return true;
}

m fauzan abdi · Answer 2 · 2018-12-24T02:21:28.737

can refer to @FernandoPelliccioni article Check string for palindrome. He did very thorough analysis for this solution.

for the simple solution:

public static boolean isPalindrome(String str) {
    return str.equals(new StringBuilder(str).reverse().toString());
}

in terms of efficiency :

public static boolean isPalindrome(String str) {
    int n = str.length();
    for (int i = 0; i < n/2; ++i) {
       if (str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true; 
}

c-an · Answer 3 · 2018-12-24T02:48:00.513

Here is a simpler way.

public boolean checkPalindrome(String str) {
    int len = inputString.length()/2;
    for(int i = 0 ; i < len ; i++) {
        if(str.charAt(i) != str.charAt(str.length()-1-i)) {
            return false;
        }
    }
    return true;
}

When the length of str is N. The time complexity is O(N/2). Note: you don't need to check the middle character when the length of str is odd because it is itself.

For example,

In ssstsss, you don't need to check t.

And since len is int. It can't express decimal part. It automatically drops. len of ssstsssis 3 because it is 7/2 = 3.5 and drops 0.5.

Even if its length is even, it will work. For example, abccba. The length is 6. And len is 3. When the length is even number, you must check even the two characters in the middle, which is cc.

score 0 · Answer 4 · answered Dec 24 '18 at 02:41

I think the easiest way is to use the default StringBuilder.
This class got a nice function wich could be usefull. It is called reverse(). It does what it says, it reverses the String wich is parsed into the StringBuilder. With this it is pretty easy to just check if the given String equals the reversed.

For example you could do:

public boolean isPallindrome(String input){
    StringBuilder reversed = new StringBuilder(input);
    reversed.reverse();
    /*
     * Just replace equals with equalsIgnoreCase
     * to ignore the case
     */
    return(reversed.toString().equalsIgnoreCase(input));
}

The given code just creates a StringBuilder instance and directly appends the input. It then reverses the StringBuilder and checks if the input equals the reversed String.

Efficient way to determine whether an input string is a palindrome or not

4 Answers4