• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Evaluate the ways of implementing isPalindrome()

 
Caly LeeAnn
Ranch Hand
Posts: 55
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There are many ways of implementing isPalindrome(), which checks whether a string or a number is a palindrome. The most common ways, I think, probably are

1. compare the first letter and the last letter, if they are the same, then move on to compare the letters at the first second place and the last second place, and so on and so forth. (Please see isPalindrome() )

2. revser the string, then compare it to the original string. (Please see isPlindrome1() )

3. recursive call. (Please see class Palindrome2 )

My question is how we should choose one over the others. How do we evaluate the performance properly?

-----

public class Palindrome {

private String pal = null;

public Palindrome(String pal) {
this.pal = pal;
}

public boolean isPalindrome(){
System.out.println(" begin: " + System.currentTimeMillis() );
boolean isPal = true;

StringBuffer sb = new StringBuffer();

for (int i=0; i<pal.length(); i++) {
char c = pal.charAt(i);
if ( Character.isLetter(c) ) {
sb.append( Character.toLowerCase(c) );
}
}

for (int i=0; i<sb.length()/2; i++) {
if ( sb.charAt(i)!= sb.charAt(sb.length()-1-i) ) {
isPal = false;
return isPal;
}
}
System.out.println(" end: " + System.currentTimeMillis() );
return isPal;
} // isPalindrome

public boolean isPalindrome1(){
System.out.println(" begin: " + System.currentTimeMillis() );
boolean isPal = true;

StringBuffer sb = new StringBuffer();

for (int i=0; i<pal.length(); i++) {
char c = pal.charAt(i);
if ( Character.isLetter(c) ) {
sb.append( c );
}
}
String str1 = sb.toString();
String str2 = sb.reverse().toString();

if ( !str1.equalsIgnoreCase( str2 ) ) {
isPal = false;
}

System.out.println(" end: " + System.currentTimeMillis() );
return isPal;
} // isPalindrome1

} // Palindrome

-----

public class Palindrome2 {
private String pal;

public Palindrome(String initPal) {
pal = initPal.toUpperCase();
}

public boolean isPalindrome() {
if (pal.length() <= 1) {
return true;
}

char first = pal.charAt(0);
char last = pal.charAt(pal.length()-1);

if (Character.isLetter(first) && Character.isLetter(last)) {
if (first != last) {
return false;
}
else {
Palindrome sub = new Palindrome(pal.substring(1,pal.length()-1));
return sub.isPalindrome();
} // if
} else if (!Character.isLetter(first)) {
Palindrome sub = new Palindrome(pal.substring(1));
return sub.isPalindrome();
} else {
Palindrome sub = new Palindrome( pal.substring(0,pal.length()-1));
return sub.isPalindrome();
}
}

} // Palindrome2
 
Reid M. Pinchback
Ranch Hand
Posts: 775
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Caly LeeAnn:
My question is how we should choose one over the others. How do we evaluate the performance properly?


One thing that comes to mind is that the "best" choice may actually differ according to the programming language unless you add an extra step before these algorithms. Languages with Pascal-ish string representations know the lengths of their strings. Languages with C-ish string representations have to scan the string to find the end. For your algorithms that would make a difference.
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic