CODEWITHSUNDEEP
javastringoptimizationpalindrome
user9237783
user9237783

Reputation:

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

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));
}

Upvotes: 3

Views: 269

Answers (4)

c-an
c-an

Reputation: 4120

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.

Upvotes: 0

Rias
Rias

Reputation: 16

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.

Upvotes: 0

m fauzan abdi
m fauzan abdi

Reputation: 436

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; 
}

Upvotes: 0

Mohamed Ibrahim Elsayed
Mohamed Ibrahim Elsayed

Reputation: 2974

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;
}

Upvotes: 5

Related Questions