Is String A Palindrome?

Is String A Palindrome?

2 Comments

Problem

You are given a string and are asked to write a method to return true if the string is a palindrome and to return false otherwise. A palindrome is a string that reads the same from front to back like alula

They are many solutions to check if a string is a palindrome. I’m going to show you three solutions. The first will use a StringBuilder and the second will use a Character Array to solve the problem. For the third solution, we will solve the problem in-place

Solution Using StringBuilder

public boolean isPalindrome(String word) {
    // create string builder
    StringBuilder sb = new StringBuilder(word);
    // reverse string builder and create new string
    String reverseWord = sb.reverse().toString();
    return word.equals(reverseWord);
}

In this solution we:

  1. Create a StringBuilder on line 3.
  2. Reverse the StringBuilder and create a new String on line 5.
  3. Use the equals method to see two strings are the same on line 6.

Solution Using CharArray

 public boolean isPalindrome(String word) {

    // create array
    char[] charArray = word.toCharArray();
    // create two index start and end
    for (int start = 0, end = word.length() - 1; start < end; ++start, --end){
      // check if the two values are  not the same
      if(charArray[start] != charArray[end]) return false;
    }
   return true;
}

In this solution we:

  1. Create a new character array on line 4 using the toCharArray() method.
  2. Loop through the array on line 6.
  3. Check if the two values are not the same on line 8. If the values are not the same we return false.
  4. Return true on line 10.

Solution In-Place

public boolean isPalindrome(String word) {
    // create two index start and end
    for (int start = 0, end = word.length() - 1; start < end; ++start, --end) {
        // check if the two values are not the same
        if (word.charAt(start) != word.charAt(end)) return false;
    }
    return true;
}

This solution is almost the same as the last one but, we use the charAt method to compare the characters. This solution is faster because it loops over the array at most once and does not use more memory.

Conclusion

You have seen different ways to check if a string is a Palindrome or not in this post. If you are asked this question in a technical interview, you will have some solutions under your belt.

 

Originally published at fluentjava.com

About Harrison Brock

Java and Go Software Engineer.

You May Also Like

2 comments on “Is String A Palindrome?

  1. February 19, 2019 at 3:03 am

    As someone who is just returning to Java Development after 15 years, I really enjoyed this post and used it somewhat as a programming kata. So thanks.

    As a born-again java newb I found the statement that the inplace version was faster was not intuitive to me, thinking that the method calls to CharAt() would be more expensive than the array access in the charArray version. So I used this as an excuse to finally try out the JMH micro benchmarking harness.
    Given the Micro benchmarks in Java are somewhat sketchy, I know that the following results should be treated with large grains of salt:
    Using:
    # JMH version: 1.19
    # VM version: JDK 11.0.2, VM 11.0.2+9
    The Score below is in nano seconds

    With 2001 Character Strings
    Benchmark Mode Cnt Score Error Units
    BenchMark.benchMarkCharArray avgt 20 1414.522 ± 43.375 ns/op
    BenchMark.benchMarkStringBuilder avgt 20 1114.262 ± 21.237 ns/op
    BenchMark.benchMarkStringInPlace avgt 20 1504.005 ± 33.689 ns/op

    With 20001 Characters String
    Benchmark Mode Cnt Score Error Units
    BenchMark.benchMarkCharArray avgt 20 13283.839 ± 216.363 ns/op
    BenchMark.benchMarkStringBuilder avgt 20 9926.038 ± 55.803 ns/op
    BenchMark.benchMarkStringInPlace avgt 20 14059.752 ± 142.771 ns/op

    With 200001 Character String
    Benchmark Mode Cnt Score Error Units
    BenchMark.benchMarkCharArray avgt 20 151697.489 ± 7796.703 ns/op
    BenchMark.benchMarkStringBuilder avgt 20 107917.317 ± 4545.513 ns/op
    BenchMark.benchMarkStringInPlace avgt 20 145527.441 ± 2362.837 ns/op

    With 2M+1 Character String
    Benchmark Mode Cnt Score Error Units
    BenchMark.benchMarkCharArray avgt 20 1846984.388 ± 68143.191 ns/op
    BenchMark.benchMarkStringBuilder avgt 20 1129483.369 ± 41332.050 ns/op
    BenchMark.benchMarkStringInPlace avgt 20 1838881.823 ± 225678.196 ns/op

    In this case it appears that the StringBuilder version has the advantage through strings up to 2M characters in size.

    I will try again later with java 8, to see if that changes things.

    Anyhow, I found this a good learning exercise, thanks for posting it.

    Reply
  2. May 10, 2019 at 10:35 am

    Thank you, super helpful

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.