I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Is This A Palindrome

07.19.2012
| 6421 views |
  • submit to reddit

It's Thursday already, so time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Is This String A Palindrome

A palindrome is a word that is exactly the same whether read forwards or backwards. What you need to do is write a function that returns true if this string provided is a palindrome. 

Catch up on all our previous puzzlers here

Comments

Vijay Nathani replied on Thu, 2012/07/19 - 2:34am

The function is builtin into Groovy library. So the code is easy in Groovy.

def boolean isPalindrome(String s) {
	s == s.reverse()
}
println isPalindrome("aba")  //prints true
println isPalindrome("abc")  //prints false

 

Vijay Nathani replied on Thu, 2012/07/19 - 2:44am in response to: Vijay Nathani

This is how Groovy codes the reverse function:

public static String reverse(String self) {
    return new StringBuilder(self).reverse().toString();
}

 

Gervais Blaise replied on Thu, 2012/07/19 - 2:45am

new StringBuilder(word).reverse().toString().equals(word) 

(Sorry, the "code" functionnality won't work)

Ankit Khandelwal replied on Thu, 2012/07/19 - 8:09am

When considering the possible solutions to a problem, we should also factor in the following points
  1. What are the limits to the domain of the problem? In this case the string which is to be checked can attain the following values
    a. string size is 0, (null or empty ): In this case the behavior of the solution should be explained.
    b. string size is infinte : In this case the behavior of the solution should be explained, may be we want to memoize the answers to longer problems and for the smaller problems we will re-compute them on the fly
  2. Another factor to consider is, "how often will this exercise be performed? or is this business logic or deployment/ops logic?". If this is a one off exercise or will be repeated only occasionally, then we can safely substitute optimizations with readability.
  3. Another factor, is this a utility function? Can this functionality be resused else where? If this functionality can indeed be reused then we want to consider, liskov substitution and open-close principle etc.

 

import java.util.HashMap;

public final class PalindromeChecker{
    private static HashMap<Integer, Boolean> cache;
    public static void main(String[] args){
        for(String arg: args){
            System.out.printf("Argument %1$s %2$s", arg, isPalindrome(arg)?" is a palindrome":" is not a palindrome");
        }
    }

    public static final boolean isPalindrome(String arg){
        if (arg == null) return false;
        int length = arg.length();
        Boolean toReturn = Boolean.FALSE;
        if (length > THRESHOLD && (toReturn = cache.get(arg.hashCode())) return 
        for(int cntr = 0, limit = length / 2; cntr < limit; cntr++){
           if (arg.charAt(cntr) != arg.charAt(length - 1 - cntr))return false;
        }
        return true;
    }
}

 

Aseem Jain replied on Thu, 2012/07/19 - 8:24am

public class PalendromePuzzle {

    public static void main(String... args){
      String string = "abcdcba ";
        System.out.println("is it palendrome " + isPalendrome(string.trim()));
    }

    private static boolean isPalendrome(String string) {
        string = string.trim();
        int stringLength = string.length();
        for(int index=0;index < stringLength/2;index++){
            if(!( string.charAt(index)== string.charAt(stringLength-index-1))){
               return false;
            }
        }
        return true;
    }
}

Joe Gerew replied on Thu, 2012/07/19 - 3:46pm

	private static boolean isPalindrome(String word){
return new StringBuilder(word).reverse().toString().equalsIgnoreCase(word);
}

Chirag Visavadia replied on Thu, 2012/07/19 - 9:02am

public class PalindromeTest {
	public static void main(String[] args) {
		String str = "abcdefghijklmnoponmlkjihgfedcba";
		boolean isPalindrome = true;
		for (int i = 0; i < str.length(); i++) {
			int len = (str.length() - 1) - i;
			// Avoid extra looping
			if (str.charAt(i) != str.charAt(len)) {
				isPalindrome = false;
				break;
			}
		}
		System.out.println("str: " + str);
		System.out.println("rev: " + new StringBuilder(str).reverse());
		System.out.println("isPalindram: " + isPalindrome);
	}
}

Chirag Visavadia replied on Thu, 2012/07/19 - 9:04am

public class PalindromeTest {

	public static void main(String[] args) {
		String str = "abcdefghijklmnoponmlkjihgfedcba";

		boolean isPalindrome = true;
		for (int i = 0; i < str.length(); i++) {
			int len = (str.length() - 1) - i;
			// Avoid extra looping
			if (str.charAt(i) != str.charAt(len)) {
				isPalindrome = false;
				break;
			}
		}
		System.out.println("str: " + str);
		System.out.println("rev: " + new StringBuilder(str).reverse());
		System.out.println("isPalindram: " + isPalindrome);
	}
}

Dino VV replied on Thu, 2012/07/19 - 12:03pm in response to: Ankit Khandelwal

Couldn't you at least compile your code to make your point? 

Ankit Khandelwal replied on Fri, 2012/07/20 - 12:31am in response to: Dino VV

@Dino VV : My apologies for the copy paste error!

Here is the corrected code.

import java.util.HashMap;

public final class PalindromeChecker{

	private static HashMap<Integer, Boolean> cache;
    
	public static void main(String[] args){
        for(String arg: args){
            System.out.printf("Argument %1$s %2$s", arg, isPalindrome(arg)?" is a palindrome":" is not a palindrome");
        }
    }

    public static final Boolean isPalindrome(String arg){
        
    	if (arg == null) return Boolean.FALSE;

        Boolean toReturn = Boolean.TRUE;
        int hashCode = arg.hashCode();
        if (toReturn = cache.get(hashCode) != null ) return toReturn;
        
        toReturn = Boolean.TRUE;
        int length = arg.length();
        for(int cntr = 0, limit = length / 2; cntr < limit; cntr++){
           if (arg.charAt(cntr) != arg.charAt(length - 1 - cntr)){
        	   toReturn = Boolean.FALSE;
        	   break;
           }
        }
        cache.put(hashCode, toReturn);
        return toReturn;
    }
    
}

 

Dino VV replied on Fri, 2012/07/20 - 8:06pm in response to: Ankit Khandelwal

One note: you shouldn't use the hashCode as a key since the hashcode of a string is not unique.

The map should be map<String, Boolean> which may defeat the optimization. 

Vijay Nathani replied on Sat, 2012/07/21 - 4:19am in response to: Dino VV

Right. The stirngs "0-42L" and "0-43-" have the same hashCode of 45721201.

Ankit Khandelwal replied on Mon, 2012/07/23 - 9:01am in response to: Dino VV

Good Point @Dino VV

But then, how does one apply memoization in such a scenario?
Even if we were to create a long or a Big Integer hashCode ( ignoring the cost of calculation of such intermediate representations), there will still be a chance for collision. So two questions arise

1. Is there some intermediate representation that will guaranty 0 collisions?
2. If there is none, then how can we minimize collision chances without using bigger intermediate representations?

Craig Lebowitz replied on Tue, 2012/07/24 - 7:59am

Please excuse the JS: 
function isPalindrome(str)
{
if(typeof(str) !== 'string') {
return false;
}

var length = str.length,
isEven = length % 2 == 0,
compareLength = isEven ? length/2 : (length-1)/2;

for(var i = 0; i < compareLength; i++)
{
if(str[i] != str[length-i-1])
return false;
}
return true;
}

Dino VV replied on Tue, 2012/07/24 - 3:22pm in response to: Ankit Khandelwal

If you want this type of optimization then you have to resort to some sort of caching map with TTL (time to live).

Then you can configure it to cache up to n items. 

Mubahser Naeem replied on Wed, 2012/07/25 - 9:20am

This is simple optimized java code to check if a string is palindrome. Please comment.

public boolean isPalindrome(String str){
        boolean flag = false;
        boolean singleCharFlag = false;
        String strFirstChar = Character.toString(str.charAt(0));
        boolean endswith = str.endsWith(strFirstChar);
        
        if(endswith){
            int strLength = str.length();
            if(strLength == 1){ singleCharFlag = true; }
            if(singleCharFlag){ return true; }
            str = str.substring(1, strLength-1);
            flag = true;
        }else{
            return false;
        }
        
        if("".equals(str)){
            return flag;
        }
        
        flag = isPalindrom(str);
        return flag;
    }

Kamala D'africa replied on Thu, 2012/07/26 - 9:02am

public static boolean isPalindrome(String str) {
	char[] chars = str.toLowerCase().toCharArray();
	int len = chars.length;
	for (int i = 0; i < len / 2; i++) {
		if (chars[i] != chars[len - i - 1]) {
			return false;
		}
	}
	return true;
}

 This takes into account that strings with mixed case are palindrome too. In terms of performance, I preferred convert input string in a char array to avoid some operation in the charAt method of class String, even though it's possible that are cases when cost of the conversion can be higher.

Kamala D'africa replied on Thu, 2012/07/26 - 9:10am in response to: Chirag Visavadia

You are almost right, but what about "abcCBA" ?

 

Marco González replied on Thu, 2012/12/20 - 9:42am

It seems nobody added a recursive solution. It is elegant and simple but not very efficient, but for the sake of this puzzler, it isn't very important.

def palindrome(phrase):
  l = len(phrase)
  if l==0 or l==1:
    return True
  else:
    return (phrase[0]==phrase[l-1]) and palindrome(phrase[1:l-1])

The reader could also remove the tail recursion.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.