4
\$\begingroup\$

I was wondering if you can give me advice on this solution to assess if an user input string is a palindrome or not. How can I optimize this solution?

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Palindrome {
public static void main(String[] args)
    throws IOException {

    // user enters string
    System.out.println ("Please enter string");

    InputStreamReader input = new InputStreamReader (System.in);
    BufferedReader reader = new BufferedReader (input);
    String userinput = "";
    userinput = reader.readLine();

    // test if string is valid
        if (!userinput.matches("[A-Za-z]+")){
            System.out.println ("Invalid Input");
            System.exit(1);
        }

        else if (userinput.length() > 10){
            System.out.println ("String too long");
            System.exit(2);
        }


    String stringReverse = "";
    for (int i = userinput.length()-1; i >= 0; i--){
        stringReverse += String.valueOf(userinput.charAt(i));
    }

    if (userinput.equals(stringReverse)){
        System.out.println ("String is a Palindrome");
        System.exit(0);
    }

    else if (userinput != stringReverse) {
        System.out.println ("String is not a Palindrome");
        System.exit(0);
    }

    }
}
\$\endgroup\$
3
\$\begingroup\$

When programming a solution like this, in order to simplify the problem create a separate function for each component. So, I would break it up into three different parts:

String getUserInput() {
    // Get input string and return it...
}

boolean isValidInput(String input) {
    // Return true or false based off of the validity of the input string.
}

boolean isPalindrome(String input) {
    int left = 0;
    int right = input.length();
    while(left < right) {
        if(input.charAt(left++) != input.charAt(--right)) return false;
    }
    return true;
}

The reason for returning a boolean rather than throwing an exception is that a try catch can be expensive especially if there is a good chance of an error being thrown. Now, a boolean means later that there may be some sort of conditional branch, but that is less expensive than if there is a high chance of an error being thrown. Also, there is more usability with returning a boolean, because now you can decide if you want to throw an exception or just print true or false.


Since the question was more geared towards the optimization of the palindrome detection algorithm, I provided a solution that I have found to work the best for when detecting palindromic inputs.

The solution cuts the number of steps down to a quarter of your solution. This is done by assuming that if the first half is the same as the second half then the String must be palindrome. So, we start from both ends and work our way to the center (essentially when left reaches or passes right). If any where along the way we find a point in which is not equal, then we know that we do not have a palindromic String. Therein, we can exit returning false. If we successfully exit the loop, then we know we were given a palindromic String. Therein, we return false.

\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to check if left is less than right. For strings of odd length, they will be the same at the middle character but for strings of even length, they will pass each other. \$\endgroup\$ – cbojar Nov 25 '16 at 23:07
  • \$\begingroup\$ Well, if you let input.length() equal 4 and input be palindromic then left => 0 and right => 4. So, first iteration they are not equivalent therein we evaluate input.charAt(0) != input.charAt(3). Second iteration left => 1 and right => 3 once again we pass so we evaluate input.charAt(1) != input.charAt(2). Third iteration left => 2 and right => 2 they are equal so we exit. So, we just evaluated every character therein none were skipped:) Yes, I could replace with a < but I get the same result with !=. Unless you can come up with a case where this is not true? \$\endgroup\$ – tkellehe Nov 25 '16 at 23:25
  • \$\begingroup\$ Right would not be 4 at the first iteration, it would be 3 because of zero based indexing. Then it would be (0, 3) => (1, 2) => (2, 1) => (0, 3) => (-1, 4) Index out of bounds. \$\endgroup\$ – cbojar Nov 26 '16 at 1:00
  • \$\begingroup\$ input.length() returns the length of the string which would be 4. \$\endgroup\$ – tkellehe Nov 26 '16 at 1:16
  • 1
    \$\begingroup\$ Not quite sure what you mean by not equal in length? How I see it with copying code is that sometimes there really is only one way to do something the fastest (in this case faster than most) therein I say copy it. If the solution is unique (unlike this code here) then I would give credit to whomever. Your implementation is streamlined, but to me my solution is just as streamlined as yours:) To me plagiarism with code is fine as long as you understand it, but that is a hard line to draw. I made that code such that others could use it and hopefully will understand it rather than just copy it. \$\endgroup\$ – tkellehe Nov 30 '16 at 13:37
1
\$\begingroup\$

You're implementation can be improved which in turn can save some memory space and execution time. Space is saved by not using another string in stringReverse and time is saved by iterating from 0 - (strlen()-1)/2 instead of 0 - strlen().

Hope this helps!

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Palindrome {
public static void main(String[] args) throws IOException {

    // user enters string
    System.out.println ("Please enter string");

    InputStreamReader input = new InputStreamReader (System.in);
    BufferedReader reader = new BufferedReader (input);
    String userinput = "";
    userinput = reader.readLine();

    // test if string is valid
        if (!userinput.matches("[A-Za-z]+")){
            System.out.println ("Invalid Input");
            System.exit(1);
        }

        else if (userinput.length() > 10){
            System.out.println ("String too long");
            System.exit(2);
        }

       //Modified this part
       int n = userinput.length();
       for (int i = 0; i <= (n - 1) / 2; i++){
         if(userinput.charAt(i) != userinput.charAt(n-1-i)) {
            System.out.println("String is not a palindrome");
            System.exit(0);
         }
       }

       System.out.println("String is a palindrome");

    }
}
\$\endgroup\$
0
\$\begingroup\$

Another way of doing it may be to create 2 indexes, the first starting from 0 and the second starting at the end of the string. Loop upon equality until they cross each other or they are not equal.

edit: Ok I am no Java specialist but the code could be something like

int a = 0;
int b = userInput.length()-1;

while (a<=b && userInput.charAt(a) == userInput.charAt(b)){
    a++;
    b--;
}

if (a>=b) {
    System.out.println("palyndrome");
} else {
    System.out.println("not palyndrome");
}
\$\endgroup\$
-1
\$\begingroup\$

Do not use System.exit() (somewhere else than in a chatch block inside main) this terminates the JVM and this is not what you want in most cases.

  // user enters string
  // test if string is valid

This type of comment tells you that the code below sould be placed in a method with a name derived from the comment. eg:

String userEntersString(){
  // ...
}

void testIfStringIsValid(String string){

}

then your main would read like this:

public static void main(String[] argd){
   String string userEntersString();
   testIfStringIsValid(string);
   testIfStringIsPalindrome(string);
   System.out.println ("String is a Palindrome");
}

To handle the validation you should have your validation method throwing Exceptions:

void testIfStringIsValid(String string) throws Exception {
    if (!userinput.matches("[A-Za-z]+")){
        throw new Exception("Invalid Input");
    }
   //...
}

then you main would change like this:

public static void main(String[] argd){
   String string userEntersString();
   try{
       testIfStringIsValid(string);
       testIfStringIsPalindrome(string);
       System.out.println ("String is a Palindrome");
   } (catch Exception e) {
       System.err.println(e.getMessage());
       // if you really need to communicate the programms result:
       System.exit(1);
   }
}
\$\endgroup\$
  • \$\begingroup\$ I could not disagree more with your use of a throw to do a basic vetting operation. You should always be looking for ways to minimise the use of exceptions and exception handling code, and you certainly should not be using expectations to pass expected information back to the method's caller. \$\endgroup\$ – Blindman67 Nov 24 '16 at 13:53
  • \$\begingroup\$ @Blindman67 "You should always be looking for ways to minimise the use of exceptions and exception handling code" hwat is the consequence og not using exceptions here? It will result in return code checks (if(isValid) then ... ) in the calling method. That is exactly the situation to be avoided and why we (except you ;o)) use exceptions. \$\endgroup\$ – Timothy Truckle Nov 24 '16 at 14:48
  • 1
    \$\begingroup\$ To use exceptions to avoid conditional statements? You are building a bridge to get over a gate. Exceptions are not an alternative to normal logic flow and adds unneeded complexity where not required. Good validation should never need to throw an exception. Exceptions are to handle what is beyond the reach of the code, the very last option when all other possibilities are exhausted. Sorry without a good reason for the throw your answer is not good advice -1 \$\endgroup\$ – Blindman67 Nov 24 '16 at 16:26
  • \$\begingroup\$ @Blindman67 "To use exceptions to avoid conditional statements?" No, that was not my statement. I use Exception to avoid checking error conditions in the "happy path". This does not mean that I don't use if statements at all. \$\endgroup\$ – Timothy Truckle Nov 24 '16 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy