Palindrome checker program

Question

I've been studying Java for some days and I'm just now starting to make some simple programs, I'd like to know if there's any 'noob' mistakes or habits that I could avoid.

In other words: how could my code be more streamlined to Java?

My code:

import java.util.Scanner;
public class Main
{
 private static String reverse_string(String my_string)
 {
 String reversed_string = "";
 for(int j = my_string.length() - 1; j >= 0; j--)
 {
 reversed_string = reversed_string + my_string.charAt(j);
 }
 return reversed_string;
 }
 public static void main(String[] args)
 {
 System.out.print("Insert a 'String': ");
 Scanner input = new Scanner(System.in);
 String user_string = input.nextLine().toLowerCase().replace(" ", "");
 if (user_string.equals(reverse_string(user_string)))
 {
 System.out.println("It is a palindrome.");
 } else
 {
 System.out.println("It is not a palindrome.");
 }
 }
}

I believe there are already other alternatives to my reverse_string function, hence the 'reinventing the wheel' tag.

• Peter Cordes: You know you don't actually have to produce a reversed copy of the string to check for palindromes, right? Use indices for the start/end and walk inwards until you meet / cross in the middle. (Handling Unicode surrogate pairs has to happen on the fly here, but I think it's possible to detect a surrogate pair when looking at the 2nd half.)
• MJ713: @PeterCordes Sounds like a good potential answer to me.
• Peter Cordes: @MJ713: A rewrite from scratch isn't really a code review. Examples of meet-in-the-middle implementations exist all over the place in all languages (although the vast majority are just for char[], not handling surrogate pairs). e.g. the canonical SO Q&A's top answer: Check string for palindrome (which happens to be in Java). Other answers there point out that Java's StringBuilder already has a .reverse() method so writing your own is unnecessary if you want simple (but inefficient) code
• MJ713: @PeterCordes Per this meta answer: "Are answers that suggest complete rewrite of the code acceptable? Yes. Always. But not a code-only 'Here is how I would do it' answer."
• Peter Cordes: @MJ713: Ah, I hadn't read that, and had the wrong impression from a comment that paraphrased it. Thanks. Anyway, given that there's a canonical Q&A about it on SO, and componentsprogramming.com/palindromes with detailed analysis of algorithm efficiency, I'm content to just link those and leave UTF-16 surrogate-pair handling as an exercise for the reader. (Especially since I don't have a Java dev env set up to test anything I might write.)

Answer 1

To answer your comment, yes there are equivalent of PEP8 in java. I suggest checkstyle, this plugin works in lots of IDE / text editors and can be configured with your code style.

Code review

reverse_string method

1. In java, we try to use the upper-case version of Snake case only on constants / enums. For the methods and variables, I suggest that you use the Camel case style.

Before

private static String reverse_string(String my_string) 
{
 //[..]
}

After

private static String reverseString(String myString) 
{
 //[..]
}

2. When concatenating String in a loop, it's generally recommended to use a java.lang.StringBuilder to gain performance and take fewer operations.

private static String reverseString(String myString) 
{
 StringBuilder reversedString = new StringBuilder();
 for (int j = myString.length() - 1; j >= 0; j--) 
 {
 reversedString.append(myString.charAt(j));
 }
 return reversedString.toString();
}

If you want not to use it, then I suggest the += operator instead of the +; it will give the same result and make the code shorter.

Other observations

The code was missing a bit of formatting, but nothing too important, I sugest that you pick a formatter for your style (Horstmann style) depending on your IDE / text editor.

Refactored code

private static String reverseString(String myString)
{
 String reversedString = "";
 for (int j = myString.length() - 1; j >= 0; j--) 
 {
 reversedString += myString.charAt(j);
 }
 return reversedString;
}
public static void main(String[] args) 
{
 System.out.print("Insert a 'String': ");
 Scanner input = new Scanner(System.in);
 String userString = input.nextLine().toLowerCase().replace(" ", "");
 if (userString.equals(reverseString(userString))) 
 {
 System.out.println("It is a palindrome.");
 } 
 else 
 {
 System.out.println("It is not a palindrome.");
 }
}

• MJ713: "Refactored code" section is still using snake case for the reversed_string variable. Also the last } is missing.
• MJ713: For clarity, you could explain that constants are written in ALL_CAPS snake case, not just any snake case.
• Peter Cordes: I'd suggest writing "Camel case" as "camelCase". When underlined as a link, it looks like capitalized Snake_case.
• Cruncher: Doesn't the official style guide for java recommend same-line braces, and not newline braces?
• MJ713: @Cruncher Whitespace actually has semantic meaning in Python, so there's both less room to play around and more reason to pay attention to style in the first place. There might also be historical factors; Python is younger than C, and its rise coincided with the rise of the web, which may have made it easier to share/enforce style standards...I'm just speculating.

Answer 2

In java is the preferred way of curly brace placing on the same line like you can see in code snippets in Oracles Style Guide.

---

reverse_string has a type embedded in its name which leads to a code smell.

The disadvantage is that if you want to change the type of the parameter you have to change the method name too.

Additional the invocation looks messy and redundant compared to a method name without the embedded type:

if (user_string.equals(reverse_string(user_string)))

compared to

if (user_string.equals(reverse(user_string)))

---

Code can be descriptive by choosing good variable names.

Scanner input = new Scanner(System.in);
String user_string = input.nextLine().toLowerCase().replace(" ", "");

I think input fits better than user_string to describe the input of a user:

Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine().toLowerCase().replace(" ", "");
if (input.equals(reverse(input))) { /*...*/ }

---

if (user_string.equals(reverse_string(user_string)))
{
 System.out.println("It is a palindrome.");
} else
{
 System.out.println("It is not a palindrome.");
}

The two System.out.println are a bit like a duplication. You could save the message you want to print in a variable and then print it once to the console:

String message;
if (user_string.equals(reverse_string(user_string))) {
 message = "It is a palindrome.";
} else {
 message = "It is not a palindrome.";
}
System.out.println(message);

Or even shorter with the ternary operator:

String message = user_string.equals(reverse_string(user_string)) ? "It is a palindrome." : "It is not a palindrome.";
System.out.println(message);

---

I know that this a small script but I would like to introduce to think in objects:

public class Main {
 private static final WhiteSpaceFreeScanner scanner = new WhiteSpaceFreeScanner(new Scanner(System.in));
 public static void main(String[] args) {
 final Input input = scanner.nextLine();
 String message = input.isPalindrome() ? "It is a palindrome." : "It is not a palindrome.";
 System.out.println(message);
 }
}

class WhiteSpaceFreeScanner {
 private final Scanner scanner;
 CustomScanner(Scanner scanner) {
 this.scanner = scanner;
 }
 Input nextLine() {
 String input = scanner.nextLine().toLowerCase().replace(" ", "");
 return new Input(input);
 }
}

class Input {
 private final String value;
 public Input(String value) {
 this.value = value;
 }
 Input reversed() { /* ... */ }
 boolean isPalindrome() {
 return this.equals(reversed());
 }
 @Override
 public boolean equals(Object o) { /* ... */ }
 @Override
 public int hashCode() { /* ... */ }
}

• Cruncher: While the object example seems clearly over-engineered to me, it is a good learning point. +1 just for composition over inheritance. EDIT: Any reason to not publicize reversed? While not required for the program specifically, it would be generally useful for the api. EDIT2: Nvm, forgot java default is same-package, not protected
• Martin Frank: String message = "It is" + (user_string.equals(reverse_string(user_string)) ? "":"not" ) +" a palindrome."; - very nice review!!!
• Martin Frank: CustomScanner would be an AlphaNumericScanner or an WhiteSpaceFreeScanner if it would remove other white space

Answer 3

Doi9t's answer is very good, but even with their improvements, there is still a problem: your code does not produce the correct answer in all cases.

Java strings use UTF-16 encoding. This means that a Java char is not large enough to store all Unicode characters. Instead some characters (for example, 😂) are stored as a pair of chars, and reversing the pair (as your code does) will result in nonsense data. See this documentation for more details.

Fortunately, the way UTF-16 is defined, chars that are surrogates (half-characters) have a completely separate range of values from chars that are Unicode characters by themselves. This means it is possible to test each char individually to see if it is a surrogate, and then have special handling to preserve the pairs.

import java.lang.Character;
import java.lang.StringBuilder;
import java.util.Scanner;
<...>
 private static String reverseString(String myString) {
 StringBuilder reversedString = new StringBuilder();
 for (int j = myString.length() - 1; j >= 0; j--) {
 char c = myString.charAt(j);
 if (Character.isLowSurrogate(c)) {
 j--;
 reversedString.append(myString.charAt(j));
 }
 reversedString.append(c);
 }
 return reversedString.toString();
 }

If you really wanted to re-invent the wheel, I think Character.isLowSurrogate(c) could be replaced with c >= '\uDC00' && c <= '\uDFFF', though I have not personally tested this.

---

As Peter Cordes pointed out in a comment, we do not even need to reverse the string in order to detect a palindrome. Instead we can examine the input string in place, comparing the first character to the last, the second to the next-to-last, etc., until we reach the middle. This may be more performant.

We need special handling for 2-char characters in this case as well; fortunately, the String class has methods for pulling code point values instead of pulling char values directly.

• codePointAt(int index) behaves similarly to charAt(int index) in most cases, but if the char at the given index is the first half of a surrogate pair, it will return the full value of the pair.
• codePointBefore(int index) approaches the problem from the other end; if the char before the given index is the last half of a surrogate pair, it will return the full value of the pair.

 private static boolean isPalindrome(String myString) {
 int len = myString.length();
 for (int i = 0; i < len / 2; ++i) {
 int frontHalfCharacter = myString.codePointAt(i);
 int backHalfCharacter = myString.codePointBefore(len - i);
 if (frontHalfCharacter != backHalfCharacter) {
 return false;
 }
 if (Character.isSupplementaryCodePoint(frontHalfCharacter)) { // i.e. if this is a 2-char character
 i++;
 }
 }
 return true; 
 }

---

And while we're on the topic of Unicode, you should of course read The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!), if you haven't already.

• TorbenPutkonen: Knowing that a letter can take two characters is vital. A close next is the StringBuilder.reverse() method. :)
• MJ713: @TorbenPutkonen They deliberately chose to do it the hard way, hence the reinventing-the-wheel tag.
• TorbenPutkonen: OP specifically asked for an alternative to the home grown reverse algorithm. The reinventing-the-wheel tag is stupid because it uses categorization tools as content and the tag name doesn't describe it's purpose. You have to go read the tag's description to figure out what it means.
• MJ713: @TorbenPutkonen OP didn't actually ask for alternatives, they just said they were aware that alternatives probably existed...but I see your point. Maybe post to codereview.meta.stackexchange.com?

Answer 4

Do you actually need to create the reversed string. Why not just go over the string from both directions.

 String palindrome = "radar";
 isPalindrome(palindrome, 0, palindrome.length() -1); 
 // Could be converted to loop if wanted.
 private static boolean isPalindrome(String candidate, int startIndex, int endIndex) {
 if(startIndex >= endIndex) {
 // Has passed each other or pointing towards same character.
 return true;
 }
 else if (candidate.charAt(startIndex) == candidate.charAt(endIndex)) {
 return isPalindrome(candidate, startIndex + 1, endIndex - 1);
 }
 return false;
 }

Answer 5

For reverse_string, it would probably be most efficient to create an array of chars and then construct a string from it. Note that I have not tested this code.

private static String reverse_string(String my_string)
{
 char[] chars = new char[my_string.length()];
 for(int i = 0; i < chars.length; ++I)
 {
 chars[i] = my_string.charAt(chars.length - 1 - i); // The two indices can be swapped
 }
 return new String(chars);
}