Determining if a sentence is a palindrome

Question

The biggest problem I see in checking palindromes on the Internet is when the user inputs a palindrome sentence or phrase and the program returns a wrong output. So for me, I tried to optimize palindrome checking by accepting sentences as input.

import java.io.*;
public class PalindromeCheck{
 public static void main(String[] args){
 BufferedReader dataIn = new BufferedReader(new InputStreamReader(System.in));
 try{
 System.out.print("Enter a sentence: ");
 String sentence = dataIn.readLine();
 PalCheck(sentence);
 }catch(IOException e){
 e.printStackTrace();
 System.err.println(e);
 }
 }
 public static void PalCheck(String s){
 String end = "";
 String result = s.replaceAll(" ", "");
 for ( int i = result.length() - 1; i >= 0; i-- )
 end = end + result.charAt(i);
 if (result.equalsIgnoreCase(end))
 System.out.println( result + " is a palindrome.");
 else
 System.out.println(result + " is not a palindrome.");
 }
}

Answer 1

The implementation given by @janos is a good one, but it is possible to improve it further. Specifically, most of the inefficiency arises from the single line:

char[] chars = string.replaceAll(" ", "").toLowerCase().toCharArray();

The replaceAll() method creates another copy of the string. Then, toLowerCase() creates another copy of the string. Finally, toCharArray() creates yet another copy in a character array of the resulting string. Of course, with the exception of the final result, the rest will get garbage collected. But each of the copies in an additional O(n) time.

Here is a suggestion:

private static boolean isPalindrome(String s) {
 int i = 0;
 int j = s.length() - 1;
 
 while (i < j) {
 if (Character.isWhitespace(s.charAt(i))) {
 i++;
 continue;
 }
 
 if (Character.isWhitespace(s.charAt(j))) {
 j--;
 continue;
 }
 
 if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
 return false;
 } else {
 i++;
 j--;
 }
 }
 return true;
}

I used the following test code to compare the performances of the two methods:

public class Main {
public static void main(String[] args) {
 String palindrome = "a b c de f g h x x xa b a xxx hg f e d c b a";
 String nonPalindrome = "abcd e f g h xxxabcxxx hgfe d c ba";
 long start = System.currentTimeMillis();
 
 for (int i = 0; i < 1000000; i++) {
 Main.checkPalindrome(palindrome);
 Main.checkPalindrome(nonPalindrome);
 }
 
 long elapsed = System.currentTimeMillis() - start;
 
 System.out.println("checkPalindrome: time elapsed: " + elapsed + " milliseconds.");
 
 
 start = System.currentTimeMillis();
 
 for (int i = 0; i < 1000000; i++) {
 Main.isPalindrome(palindrome);
 Main.isPalindrome(nonPalindrome);
 }
 
 elapsed = System.currentTimeMillis() - start;
 
 System.out.println("isPalindrome: time elapsed: " + elapsed + " milliseconds.");
 
 
}
private static boolean isPalindrome(String s) {
 int i = 0;
 int j = s.length() - 1;
 
 while (i < j) {
 if (Character.isWhitespace(s.charAt(i))) {
 i++;
 continue;
 }
 
 if (Character.isWhitespace(s.charAt(j))) {
 j--;
 continue;
 }
 
 if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
 return false;
 } else {
 i++;
 j--;
 }
 
 }
 
 return true;
}
private static boolean checkPalindrome(String string) {
 char[] chars = string.replaceAll(" ", "").toLowerCase().toCharArray();
 for (int i = 0; i < chars.length / 2; ++i) {
 if (chars[i] != chars[chars.length - 1 - i]) {
 return false;
 }
 }
 return true;
}
}

Running on my computer produced the following result:

checkPalindrome: time elapsed: 7373 milliseconds.

isPalindrome: time elapsed: 421 milliseconds.

Answer 2

While your solution works, it's very poorly written.

Single responsibility principle

It's good that you separated the user input part and the rest. But you could go further.

The PalCheck method has too many responsibilities:

• It checks if the input is a palindrome
• It prints the result

It would be better to use separate methods for these. An intuitive name for a method that checks if a string is a palindrome or not would be isPalindrome. A void checkPalindrome method could call isPalindrome and print the result.

Unit testing

One of the great advantages of separating responsibilities is testability. You should write unit tests to verify your implementation easily, which is only possible when methods have a single responsibility.

Some example unit tests:

@Test
public void test_hello_is_not_palindrome() {
 assertFalse(isPalindrome("hello"));
}
@Test
public void test_hello_olleh_is_palindrome() {
 assertTrue(isPalindrome("hello olleh"));
}
@Test
public void test_aba_is_palindrome() {
 assertTrue(isPalindrome("aba"));
}
@Test
public void test_x_palindrome() {
 assertTrue(isPalindrome("x"));
}
@Test
public void test_xx_palindrome() {
 assertTrue(isPalindrome("xx"));
}
@Test
public void test_empty_palindrome() {
 assertTrue(isPalindrome(""));
}

Bad practices and inefficiencies

Instead of this:

 end = end + result.charAt(i);

This is shorter:

 end += result.charAt(i);

However, note that string concatenation in a loop is known to be inefficient and a bad practice. You should use a StringBuilder for this kind of thing.

---

It would be better to use braces for the body of the for loop and the if-else statements too, even if the body is a single statement. Not using braces consistently everywhere can potentially lead to mistakes and horrible bugs.

---

Instead of using result.equalsIgnoreCase(end), it would be more efficient to convert the input to lowercase early, and in the end use simple .equals in the comparison.

Naming

Methods should be named with camelCase, not PascalCase.

result and end are very poor names. They don't describe the purpose of the variables.

Suggested implementation

Here's an alternative implementation that's much more efficient:

private boolean checkPalindrome(String string) {
 String text = string.replaceAll(" ", "").toLowerCase();
 int len = text.length();
 for (int i = 0; i < len / 2; ++i) {
 if (text.charAt(i) != text.charAt(len - 1 - i)) {
 return false;
 }
 }
 return true;
}

• ComFreek: It should be added that the method checkPalindrome() will fail for "non-trivial" characters (e.g. surrogate pairs in Unicode / UTF-16).

Answer 3

• instead of BufferedReader you should use Scanner
• importing everything of a namespace import java.io.*; is bad practice

• user35408: What are the advantages of Scanner over BufferedReader? Why should the questioner use one or the other?

Answer 4

Few tips:

• Imports: Check if its required. If yes, be specific.
• Have only those statements in try..catch which you know can lead to an exception.
• Have a custome message printed to the user during any exception along with the cause. (StackTrace is just for you).
• Check if s is null/empty because result.length() can be zero.
• Redundant overheads include:
  1. Having end.
  2. Running a for loop to populate end.
  3. Having another loop to check result and end.
     

     Follow safKan's algo to optimise the same.

• Since bitwise operation is faster, a small trick to convert uppercase to lowercase (OR the character with 32):

  • 'A'|32 = 'a'
  • 'a'|32 = 'a'

Answer 5

public static void PalCheck(String s){
String end = "";
String result = s.replaceAll(" ", ""); /***I believe this is a wrong move **/
 for ( int i = result.length() - 1; i >= 0; i-- )
 end = end + result.charAt(i);
 if (result.equalsIgnoreCase(end))
 System.out.println( result + " is a palindrome.");
 else
 System.out.println(result + " is not a palindrome.");
}
}

Try the program with "Noel eleon"

When you take out the spaces like your script does, it becomes "Noeleleon" which is a palindrome but the input isn't!

The following code follows strict palindrome rules

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
 /**
 *
 * @author ramnath
 */
 public class TestAnagram {
 public static boolean isAnagram(String first) {
 int i,j,mid;
 String positive = first.toLowerCase();
 mid=positive.length()/2;
 if((positive.length()%2)==0){
 i=mid-1;j=mid;
 }
 else{
 i=mid-1;j=mid+1;
 }
 while(i>=0){
 int front=(int) positive.charAt(i);
 int rear=(int) positive.charAt(j);
 if(front==rear){
 i--;j++;
 }
 else{
 System.out.println("not a palindrome");
 return false;
 }
}
 System.out.println(positive+" is a palindrome");
 return true;
}
public static void main(String[] args) {
System.out.println(isAnagram("Noel o leon")); // true
System.out.println(isAnagram("Noel oo leon")); // true
System.out.println(isAnagram("Noel io leon")); // false
System.out.println(isAnagram("Noel eleon")); // false
System.out.println(isAnagram("Noel oo ini oo leon")); // true
System.out.println(isAnagram("Sore was I ere I saw Eros")); // true
}
}

• SuperBiasedMan: Welcome to Code Review! You should add more information about what your code changes and how it enforces strict pallindromes.