PDA

View Full Version : Java Homework (Palindrome)




zechmann
Oct 28, 2007, 09:53 PM
so we need to ask someone to input a sentence and the program will check if the sentence is a palindrome... what method could i use to accomplish this? I don't think a tokenizer would work because it shouldn't count spaces, or symbols (@,$) when checking if it is a palindrome.... thanks for ANY help



mlw1235
Oct 28, 2007, 11:01 PM
Take the input string, and put it into an array using a combination of loops and the "substring" method.

From there, iterate through the array seeing if array.length - x and x are the same.

robbieduncan
Oct 29, 2007, 02:24 AM
This would appear to be very simple (code untested, just typed straight in here):



public boolean isPalindrome(String input)
{
int index = 0;
Character a,b;
int length = input.length/2; // Note that this will automatically ignore the middle character on a string with an odd length
while (index<length)
{
a = new Character(input.charAt(index));
b = new Character(input.charAt(input.length-1-index));
if (a.isLetter() && !b.isLetter() ||
!a.isLetter() && b.isLetter())
{
// One of the character is a letter and the other isn't
return false
}
if (a.isLetter() && b.isLetter() && a.compareTo(b)!=0)
{
// Both are letters, but one letter is different to the other
return false;
}
++index;
}

return true;
}



So how does it work? It peals the characters off the string from both ends checks if they should be compared and compares them if they should be. If it reaches the middle of the string without issue returns true.

So on a string like "aba" length will be 1. Character a will be a, Character b will be a and these will match. Index will increase to 1 and the loop will terminate.

Note the if statements could be collapsed and probably be made more minimal in terms of comparisons: I chose these for readability.

elppa
Oct 29, 2007, 06:09 AM
StringBuilder has a reverse method.

ChrisBrightwell
Oct 30, 2007, 12:00 AM
Use String.compareToIgnoreCase() and StringBuffer.reverse().

You'll have to figure out how to account for whitespace and punctuation, but that should be the easy part. :)

zechmann
Oct 30, 2007, 03:54 AM
im stuck here...


import java.io.*;
import java.util.*;
public class PalindromeDetector
{
public static void main(String[] args)
throws java.io.IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String palin1;

System.out.print("Input text? ");
palin1 = br.readLine();
StringBuffer palin2 = palin1.reverse();
System.out.println(palin1);
System.out.println(palin2.toString());
}
}




says there is something wrong with the .reverse();

jeremy.king
Oct 30, 2007, 09:40 AM
says there is something wrong with the .reverse();

reverse() is a StringBuffer method, not String.

ChrisBrightwell
Oct 30, 2007, 10:16 AM
says there is something wrong with the .reverse();

Convert the input to a StringBuffer. The .reverse() method is a member of StringBuffer, not String.

zechmann
Oct 30, 2007, 06:53 PM
how do you convert a string to a stringbuffer?


import java.io.*;
import java.util.*;
public class PalindromeDetector
{
public static void main(String[] args)
throws java.io.IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String palin1;

System.out.print("Input text? ");
palin1 = br.readLine();
StringBuffer palin2 = palin1;
StringBuffer palin3 = palin2.reverse();
System.out.println(palin1);
System.out.println(palin3.toString());
}
}

ChrisBrightwell
Oct 30, 2007, 07:47 PM
how do you convert a string to a stringbuffer?

Learn to read the javadoc.

http://java.sun.com/j2se/1.5.0/docs/api/java/lang/StringBuffer.html

zimv20
Oct 30, 2007, 08:09 PM
loops are for stanleys. use recursion.

zechmann
Oct 30, 2007, 08:48 PM
when comparing the two strings how do you get it to ignore
1. spaces
2. Punctuations (,?)
3. and the case of the characters


import java.io.*;
import java.util.*;
public class PalindromeDetector
{
public static void main(String[] args)
throws java.io.IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String palin1;

System.out.print("Input text? ");
palin1 = br.readLine();

StringBuffer palin2 = new StringBuffer(palin1);
StringBuffer palin3 = palin2.reverse();
String palin4 = palin3.toString();



if(palin1.equals(palin4))
{
System.out.println("This is a palindrome.");
}
else
{
System.out.println("This is not a palindrome.");
}
}
}

unsanity
Oct 30, 2007, 09:07 PM
I wrote this exact program a while back using arrays instead of strings/stringbuffers. I just added each of the characters in the input string to an array in order and then i did the same thing except backwards, and for both of these I just had it skip any characters that weren't letters. Then I simply compared the two arrays.

zechmann
Oct 30, 2007, 09:24 PM
so how do you make it skip blank spaces and punctuations(, . ? ;)?

ChrisBrightwell
Oct 30, 2007, 09:58 PM
so how do you make it skip blank spaces and punctuations(, . ? ;)?

Scan the buffer for the characters you want to ignore ... and ... IGNORE THEM. :P

robbieduncan
Oct 30, 2007, 10:13 PM
so how do you make it skip blank spaces and punctuations(, . ? ;)?

I'd just use the regexp based method replaceAll defined on String to remove them all before the reversal (assuming you want to keep doing it this way: the code I posted does it without reversal).

Something like


noPunctuation = palin1.replaceAll("\W",'')


should work fine (\W is the character class of all non-word characters).

Gelfin
Oct 31, 2007, 03:07 AM
Hint for future reference: You will see problems like this in technical job interviews. Generally speaking, if you can't do it in place, you don't get the job. Trust me. No offense to those who suggested reversing a copy of the string, but this problem explicitly divides prospective programmers into "people who do that" and "people who don't." Don't even think of using a regexp, as that is a little like being asked how you would change a car tire and answering, "first, I would rent a crane..."

The code robbieduncan posted is on the right track, but solves a slightly different problem than the one described. His solution does not ignore non-letters, but instead matches them against any other non-letter character. They still count. The problem described should count "$$$ab cd.cba3" as a palindrome. This can be done quite easily with an adaptation of robbieduncan's code.

zechmann
Oct 31, 2007, 03:15 AM
yea i understand my coding is off but had to miss class (for econ) so I need to learn about arrays... also I am majoring in MIS and marketing so java isn't technically too important... though i take it seriously because it does interest me... btw finished it, thanks for the help guys

robbieduncan
Oct 31, 2007, 03:16 AM
The code robbieduncan posted is on the right track, but solves a slightly different problem than the one described. His solution does not ignore non-letters, but instead matches them against any other non-letter character. They still count. The problem described should count "$$$ab cd.cba3" as a palindrome. This can be done quite easily with an adaptation of robbieduncan's code.

I can't really disagree with that. What you should probably actually do is use the method toCharArray() (http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html#toCharArray()) to turn the string into an array of characters and then walk that from both ends skipping over non-characters encountered at either end. As soon as the indexes meet you are done. Note that this is not really in-place: you have created a new array to do this.

Gelfin
Oct 31, 2007, 04:09 AM
Indeed, and you can avoid the array copy trivially. Since the homework has already been turned in...


public boolean isPalindrome(String input)
{
boolean bPalindrome = true;
// Work from both ends of the string towards the middle.
int nStart = 0;
int nEnd = input.length() - 1;
while(bPalindrome && nStart < nEnd)
{
if(!Character.isLetter(input.charAt(nStart)))
{
// Ignore nonletters at the beginning.
nStart++;
}
else if(!Character.isLetter(input.charAt(nEnd)))
{
// Ignore nonletters at the end.
nEnd--;
}
else if(Character.toLowerCase(input.charAt(nStart)) == Character.toLowerCase(input.charAt(nEnd)))
{
// These characters match. Advance to the next pair.
nStart++;
nEnd--;
}
else
{
// Mismatch. Fail.
bPalindrome = false;
}
}
return bPalindrome;
}


I tested this in the context of a JSP (which is quicker to evaluate with in my current dev environment) and it seems to do the right thing. There are a few things I could have done differently, like use a break instead of testing bPalindrome each iteration, but I think this is the clearer presentation.

Update: It occurred to me after posting that most palindromes will require a case-insensitive comparison. E.g., "Madam, I'm Adam." Added toLowerCase in the comparison to compensate.

Zortrium
Oct 31, 2007, 05:25 AM
Recursion hasn't gotten nearly enough love in this thread.

public boolean isPalindrome( String s ){
int len = s.length();
if( len == 1 )
return true;
else if( len == 2 )
return s.charAt( 0 ) == s.charAt( 1 );
else
return ( s.charAt( 0 ) == s.charAt( len - 1 ) ) && isPalindrome( s.substring( 1, len - 1 ) );
}

robbieduncan
Oct 31, 2007, 06:34 AM
@Gelfin, The one thing I don't like about this solution (and the one I originally posted) is the creation of all the temporary character objects. Whilst the garbage collector is pretty good at clearing these up (and they may actually be immutable instances so repeated characters cost nothing) it still seems wasteful to create all these objects. Unfortunately I could not find a way of testing if a char was a letter.

@Zortrium Recursion is a cool technique, but it can be quite expensive: method calls definitely have cost.

Gelfin
Oct 31, 2007, 09:27 AM
@Gelfin, The one thing I don't like about this solution (and the one I originally posted) is the creation of all the temporary character objects. Whilst the garbage collector is pretty good at clearing these up (and they may actually be immutable instances so repeated characters cost nothing) it still seems wasteful to create all these objects. Unfortunately I could not find a way of testing if a char was a letter.

Look again. You created lots of Character objects, but I didn't create any. The character utility functions are static for exactly that reason. Character.isLetter(x) is the way to test. Even if you didn't have that, you can still use comparison operators on primitive types:


if((x >= 'A' && x <= 'Z') || (x >='a' && x <= 'z')) {...}


@Zortrium Recursion is a cool technique, but it can be quite expensive: method calls definitely have cost.

Agreed, but it isn't just the stack overhead that kills that solution. Look at how many substrings are being created. For a 10-character string, that recursive solution allocates and copies up to another 45 characters of string data, in 9 distinct Strings. Those substrings aren't free just because you created them on the stack, or because they aren't in your current stack frame. The .reverse-based solutions are actually far more efficient than recursion in this case.

Don't recurse just to prove you know how to recurse unless that's explicitly what you are being asked to do. You need to examine the problem in front of you and compare the alternatives.

Persifleur
Oct 31, 2007, 11:51 AM
Agreed, but it isn't just the stack overhead that kills that solution. Look at how many substrings are being created. For a 10-character string, that recursive solution allocates and copies up to another 45 characters of string data, in 9 distinct Strings. Those substrings aren't free just because you created them on the stack, or because they aren't in your current stack frame. The .reverse-based solutions are actually far more efficient than recursion in this case.

Actually, substring() is a bit more intelligent than that. All the Strings created using substring() will use the same underlying character array (since Strings are immutable in Java). A new String container will still be created for each substring, which still makes the loop more efficient.

savar
Oct 31, 2007, 12:39 PM
Hint for future reference: You will see problems like this in technical job interviews. Generally speaking, if you can't do it in place, you don't get the job. Trust me. No offense to those who suggested reversing a copy of the string, but this problem explicitly divides prospective programmers into "people who do that" and "people who don't." Don't even think of using a regexp, as that is a little like being asked how you would change a car tire and answering, "first, I would rent a crane..."

Moreover, I'm sure the point of the exercise wasn't to learn how to use the functions reverse() and compare(), it was to test the critical thinking skills of how do you translate your [human] understanding of the problem into a detailed set of computer instructions which solve that problem.

"return s1.compare(s2.removeSpaces().reverse())" is not solving the problem, it's just reusing somebody else's solutions to similar problems. Honestly, you shouldn't be tested on things like this. My personal belief is that anything that is documented does not need to be memorized, only familiarized. When you get job writing code, it's not like your boss ever says, "Finish this assignment without looking at any documentation."

Quite the opposite, actually -- you'll rely on documentation extensively. So the exact names and arguments don't matter 1/100th as much as developing the ability* to translate problems understood or explained in human terms into the radically different notion of a computer language.

*As a corollary, I also believe that some people are simply incabable of the level of abstraction required to translate human problems into computer solutions.

Gelfin
Oct 31, 2007, 01:00 PM
Actually, substring() is a bit more intelligent than that. All the Strings created using substring() will use the same underlying character array (since Strings are immutable in Java). A new String container will still be created for each substring, which still makes the loop more efficient.

Ooo, darn meddling kids. You got me. :-)

robbieduncan
Oct 31, 2007, 04:45 PM
Look again. You created lots of Character objects, but I didn't create any. The character utility functions are static for exactly that reason. Character.isLetter(x) is the way to test. Even if you didn't have that, you can still use comparison operators on primitive types:


if((x >= 'A' && x <= 'Z') || (x >='a' && x <= 'z')) {...}


<homer>Doh!</homer> Sorry! Spent too long at work looking, mostly, at Java code! I don't personally like the primitive comparisons. The assumption there is that we are using the "standard" 26 character alphabet. I'm pretty sure that would not count as a letter, but isLetter() would.

Zortrium
Oct 31, 2007, 05:09 PM
Slight efficiency losses aside, recursion still strikes me as the most elegant and readable solution-then again, my current recursion tendencies may largely be that I've been doing Lisp recently. ;)