12
\$\begingroup\$

My objective is to take a string as input and determine if it is a palindrome. I'm wondering how I could improve this code (efficiency, bugs, etc). I'm relatively new to Java so I'm expecting that my code will contain some errors.

import java.util.Scanner;

    /**
     * Created by Adam on 6/5/2015.
     */
    public class Reversal {
        public static void main(String args[]) {
            String word = "";
            String reversed = "";
            Scanner in = new Scanner(System.in);
            System.out.println("Please enter the string: ");
            word = in.nextLine();
            int length = word.length();
            for(int i = length; i > 0; i--) {
                reversed += word.charAt(i-1);
            }
            if(removeSpace(word).compareTo(removeSpace(reversed)) == 0) {
                System.out.println("The string " + word + " is a palindrome");
            }
            else {
                System.out.println("The string " + word + " is not a palindrome");
            }
        }

        private static String removeSpace(String aword) {
         String buffer = "";
            for(int i = 0; i < aword.length(); i++)   {
             if(!(String.valueOf(aword.charAt(i)).compareTo(" ") == 0)) {
                 buffer += aword.charAt(i);
             }
         }
            return buffer;
        }
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Posting this answer for problem solving, and not as a review or cleanup of your own code, but you could use word = word.replace(" ","").toUpperCase(); to remove spaces and make everything the same capitalization, and then for checking if a palindrome for(int i=0; i<word.length()/2;i++){ if(word.charAt(i)==word.charAt(word.length-1-i)){ return false; }} return true; This will compare all the characters from the beginning with the end, up until the midpoint. If it doesn't return false by the end, then it is true! Hopefully this is helpful in more of a problem solving sense in the future. \$\endgroup\$ – JPMC Jun 6 '15 at 3:51
  • \$\begingroup\$ crepes, it won't let me edit my comment after 5 minutes, I realized that "==" should be "!=" \$\endgroup\$ – JPMC Jun 6 '15 at 4:04
  • \$\begingroup\$ Cross-posted? stackoverflow.com/questions/30683062/… \$\endgroup\$ – user35443 Jun 6 '15 at 13:47
20
\$\begingroup\$

Firstly, this is something I see a distressing amount in beginner Java programmers:

removeSpace(word).compareTo(removeSpace(reversed)) == 0

There's a method for checking if two Strings are equal. It's called equals. It'd be used like this:

removeSpace(word).equals(removeSpace(reversed))

If you wanna ignore case, you could use equalsIgnoreCase:

removeSpace(word).equalsIgnoreCase(removeSpace(reversed))

Secondly, a formatting tip: Except in method declarations or calls, always put a space before ( and a space after ). So, for example:

if(...) {

becomes

if (...) {

In your removeSpaces method:

  • In general, when find that you're doing it a lot, avoid using String += String. Instead, initialize a StringBuilder and append to it.
  • String#charAt() returns a char, which can be compared with ==; I'm not sure why you first turn it into a String, then use compareTo (which, again, should be equals, since you were comparing Strings for equality)

With those issues fixed, this is what the method looks like:

private static String removeSpace(String aword) {
     StringBuilder buffer = new StringBuilder();
        for (int i = 0; i < aword.length(); i++)   {
         if (aword.charAt(i) != ' ')) {
             buffer.append(aword.charAt(i));
         }
     }
     return buffer.toString();
}

(Note that I changed what would have been !(... == ...) to ... != ... and that ' ' uses single quotes.)

The whole function could be replaced with word.replaceAll(" ", ""), but that's no fun, so I'm gonna keep using yours through here. Besides, it's a good way to practice to write your own methods -- just remember, when you're writing production code, to do a thorough search of the docs first. If there's a version in the standard API, a whole gaggle of people have been optimizing it to high heaven, and it might even be implemented in native code. That alone would make it a bazillion times faster than anything you could write in pure Java.

You use removeSpaces in the comparison, which somewhat obfuscates what really happens: The String is checked for palindromity (word coined?) ignoring the spaces. It's clearer to move those method calls to when you get it (plus, this removes an extra function call, which is more efficient :D):

word = removeSpaces(in.nextLine());
// ...
if(word.equals(reversed)) { // Note that I'm not using compareTo here
// etc.

Thirdly, I'd recommend pulling the code that reverses your String into another method that takes a String argument and returns a String (and applying my earlier advice about StringBuilder):

public static String reverse(String word) {
    StringBuilder reversed = new StringBuilder(word.length);
    for(int i = word.length(); i > 0; i--) {
        reversed.append(word.charAt(i - 1));
    }
}

In that snippet above, I also removed length, since it's ultimately useless. You're only using it once, so there's no point in declaring a variable, and it's actually clearer to be able to directly see what String's length we're talking about -- you don't need to go back in the code to see what it means

With all this, your main becomes a bit clearer:

public static void main(String args[]) {
    String word = "";
    String reversed = "";
    Scanner in = new Scanner(System.in);
    System.out.println("Please enter the string: ");
    word = removeSpaces(in.nextLine());
    reversed = reverse(word);
    if (word.equals(reversed)) {
        System.out.println("The string " + word + " is a palindrome");
    }
    else {
        System.out.println("The string " + word + " is not a palindrome");
    }
}

We could clean it up a little more by moving your word and reversed declarations to where the variables are first assigned, rather than their own lines (which, incidentally, don't need the = "" because they aren't used before you assign them later):

public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    System.out.println("Please enter the string: ");
    String word = removeSpace(in.nextLine());
    String reversed = reverse(word);
    if (word.equals(reversed)) {
        System.out.println("The string " + word + " is a palindrome");
    }
    else {
        System.out.println("The string " + word + " is not a palindrome");
    }
}

This means that your whole class, all together, looks something like this:

public class Reversal {
    public static String reverse(String word) {
        StringBuilder reversed = new StringBuilder(word.length);
        for (int i = word.length(); i > 0; i--) {
            reversed.append(word.charAt(i - 1));
        }
    }

    private static String removeSpace(String aword) {
         StringBuilder buffer = new StringBuilder();
            for (int i = 0; i < aword.length(); i++)   {
             if(aword.charAt(i) != ' ')) {
                 buffer.append(aword.charAt(i));
             }
         }
         return buffer.toString();
    }

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        System.out.println("Please enter the string: ");
        String word = removeSpace(in.nextLine());
        String reversed = reverse(word);
        if (word.equals(reversed)) {
            System.out.println("The string " + word + " is a palindrome");
        }
        else {
            System.out.println("The string " + word + " is not a palindrome");
        }
    }
}

If you want to get rid of your custom method to remove spaces (which I would recommend doing if you ever had to remove spaces in production code):

public class Reversal {
    public static String reverse(String word) {
        StringBuilder reversed = new StringBuilder(word.length);
        for (int i = word.length(); i > 0; i--) {
            reversed.append(word.charAt(i - 1));
        }
    }

    private static String removeSpace(String aword) {
         StringBuilder buffer = new StringBuilder();
            for (int i = 0; i < aword.length(); i++)   {
             if(aword.charAt(i) != ' ')) {
                 buffer.append(aword.charAt(i));
             }
         }
         return buffer.toString();
    }

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        System.out.println("Please enter the string: ");
        String word = in.nextLine().replaceAll(" ", "");
        String reversed = reverse(word);
        if (word.equals(reversed)) {
            System.out.println("The string " + word + " is a palindrome");
        }
        else {
            System.out.println("The string " + word + " is not a palindrome");
        }
    }
}

And, finally, an utterly unreadable version of your code that does the same thing, which you should never use but was annoyingly fun to write so I thought I'd provide it anyway:

public static void main(String args[]) {
    String l;
    System.out.println("The string "+(l=new Scanner(System.in).nextLine())+" is"+(l.replaceAll(" ", "").equals(new StringBuilder(l).reverse().toString().replaceAll(" ", ""))?" ":" not ")+"a palindrome");
}
\$\endgroup\$
  • \$\begingroup\$ Thanks you for the advice. As for your two line main example, I've never seen the ? : syntax used before (So I googled it). Is it bad practice to use such syntax, or are you saying the code is bad because it is difficult to read? \$\endgroup\$ – adam19325 Jun 6 '15 at 23:19
  • \$\begingroup\$ @adam19325 It's perfectly fine practice when you know what you're doing. That whole chunk of code is bad because it's unreadable, not because it has a ternary operator. (Though the ternary does make it rather harder to understand) \$\endgroup\$ – Nic Hartley Jun 7 '15 at 0:13
13
\$\begingroup\$

CODING STYLE

For the beginning, some coding habits you seem to have picked up could/should be changed. Declare your variables before use, not at beginning of the method (does not apply for loops, where you deliberately want to declare variable before loop). This was, and still is, widely used in C/C++. Earlier was possible to declare new variables only at beginning of the function, and it sticked with some programmers. Declaration before first use makes code more readable, because at beginning of a function you read some listed variables you do not know what they are for, and later on you see some of them used but do not already remember initial state for instance.

Insert empty lines between logic blocks, it makes code more readable and one can by a quick glance guess what is that block about and move along. It is also common to write comment for whole block after that empty line (if it is necessary).

Do not use articles in your naming. I suppose that is an article in variable "aword". You could be more descriptive about purpose of variables. Naming your variables in removeSpace to input/output instead of aword and buffer will leave no doubts about their purpose.

Naming of your method "reverseSpace" is unclear, because "space" is singular, which without javadoc or looking at the code says only one space will be removed. Correct name would be with plural "removeSpaces".

CODE

When you are doing something fairly simple, always consider looking for some one liner, which pays especially for operations over strings.


Reverse string can be done by

String output = new StringBuilder(input).reverse().toString();

Google: "java reverse string"


Spaces can be removed by

String output = input.replaceAll("\\s+","");

or if you want to remove only space and not all whitespaces

String output = input.replaceAll(" ","");

Google: "java remove whitespaces"


In condition for comparing of reversed with original, you used function compareTo. This is unnecessary and not exactly obvious at first glance. Much more suitable is using object method equals.

if(removeSpace(word).equals(removeSpace(reversed)))

Your code could be more optimal, because you unnecessarily call removeSpace twice, when you need to call it only after reading the input.

Another optimization would take away the reversal of the string altogether. You can just iterate over the elements and look at opposite index.

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

Hope this helps, regards.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'd like to note that you should have a space around your operators (<, !=, etc.) \$\endgroup\$ – Nic Hartley Jun 6 '15 at 2:57
  • 1
    \$\begingroup\$ Also, don't declare your variables before for loops! Declare them ** the loop! \$\endgroup\$ – Nic Hartley Jun 7 '15 at 0:14
  • \$\begingroup\$ @QPaysTaxes That is simply wrong advice. When you do want to do incremental work over variable in the loop, you declare it before the loop out of principle, which is exactly what I mentioned in my answer. I guess someone could interpret it wrong, and declare them there always, but this generalization does not help at all. \$\endgroup\$ – Vojtěch Kaiser Jun 7 '15 at 13:32
  • 1
    \$\begingroup\$ I see what you mean, but generally I use while loops for that kind of thing, since it's simpler for me to understand, so I didn't think of that. \$\endgroup\$ – Nic Hartley Jun 7 '15 at 13:33
  • 1
    \$\begingroup\$ It's no different. My point was that I didn't consider that situation because it never happens to me; in my personal coding experience, iteration variables are always declared in the for loop, hence my slightly wrong comment. \$\endgroup\$ – Nic Hartley Jun 7 '15 at 13:39
8
\$\begingroup\$

A general rule about efficiency:
Appending a String to another String inside a loop is very inefficient. You're creating a lot of unneeded String objects this way:

for(int i = length; i > 0; i--) {
    reversed += word.charAt(i-1);
}

Instead, use a StringBuilder to append Strings together:

StringBuilder reversed = new StringBuilder();
for (int i = length; i > 0; i--) {
    reversed.append(word.charAt(i-1));
}

However, you don't need this loop, because StringBuilder has a reverse method. How convenient!

String reverse = new StringBuilder(word).reverse().toString();

You are also creating an unneeded String in this line:

if(!(String.valueOf(aword.charAt(i)).compareTo(" ") == 0))

You can just compare 2 characters instead of 2 Strings:

if (aword.charAt(i) != ' ')

But, again, you don't need it; the String class already has a method for it. Just replace all spaces with the empty String:

word = word.replace(" ", "");

But
...

You don't need any of this. The way you go about solving your problem is long-winded and inefficient to begin with. Think about what you're doing.
If a String is a palindrome (if you forget about spaces for a moment), then:
the 1st character is equal to the last character, and
the 2nd character is equal to the second-to-last-character,
etc.
This can be done in one for-loop: compare the first and last character and move towards the middle. You only need an extra check to skip the spaces.

private static boolean isPalindromeWithoutSpaces(string input) {
    int left = 0, right = input.length() - 1;
    while (left < right) {
        char leftChar = input.charAt(left);
        char rightChar = input.charAt(right);
        if (leftChar == ' ') {
            left++;
        } else if (rightChar == ' ') {
            right--;
        } else if (leftChar != rightChar) {
            return false;
        } else {
            left++;
            right--;
        }
    }
    return true;
}

This does not create any new objects whatsoever and only loops over the entire String just once.

\$\endgroup\$
5
\$\begingroup\$

Wouldn't recursion be better for this? I made a palindrome checker not too long ago and I use recursion too check the first and last character of the string and continue too work my way inwards.

public class Palindrome
{
   public static void main (String [] args)
   {
      String st = "radar";
      if (palindrome (st, 0, st.length() - 1)){
         System.out.println ("It is a palindrome :)");
      }
      else{
         System.out.println ("Not a palindrome :(");
      }
   }

   private static boolean palindrome (String s, int start, int end)
   {
      if (start >= end){
        return (true);
      }
      else{
        if (s.charAt(start) != s.charAt(end)){
          return (false);
        }
        else{
          return (palindrome (s, start + 1, end - 1));    
        }
      }
   }
}

As I said above this recursion takes the first and last character of the string and compares them. If they are equal it'll proceed with the second and beforelast characters. Therefore you won't have too reverse the string.

As soon as it finds a set of characters that's not the same it will immediatly return false and not check the rest of the string, which makes it more efficient.

\$\endgroup\$
  • 2
    \$\begingroup\$ This is not a python. Always put braces around your branches event if they contain only one statement. It is common source of bugs. \$\endgroup\$ – Vojtěch Kaiser Jun 6 '15 at 15:13
  • \$\begingroup\$ You are right, bad habbit of mine. I've added them. \$\endgroup\$ – RemcoW Jun 6 '15 at 15: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.