Mac Java Homework (Palindrome)

zechmann

macrumors member
Original poster
May 8, 2007
92
0
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

macrumors 6502
Jul 16, 2004
270
0
Milwaukee, WI
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

Moderator emeritus
Jul 24, 2002
24,766
134
Harrogate
This would appear to be very simple (code untested, just typed straight in here):

Code:
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.
 

ChrisBrightwell

macrumors 68020
Apr 5, 2004
2,294
0
Huntsville, AL
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

macrumors member
Original poster
May 8, 2007
92
0
im stuck here...

Code:
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();
 

zechmann

macrumors member
Original poster
May 8, 2007
92
0
how do you convert a string to a stringbuffer?

Code:
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());
        }
}
 

zechmann

macrumors member
Original poster
May 8, 2007
92
0
when comparing the two strings how do you get it to ignore
1. spaces
2. Punctuations (,?)
3. and the case of the characters

Code:
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

macrumors newbie
Jul 27, 2005
26
0
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.
 

robbieduncan

Moderator emeritus
Jul 24, 2002
24,766
134
Harrogate
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

Code:
noPunctuation = palin1.replaceAll("\W",'')
should work fine (\W is the character class of all non-word characters).
 

Gelfin

macrumors 68020
Sep 18, 2001
2,166
4
Denver, CO
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

macrumors member
Original poster
May 8, 2007
92
0
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

Moderator emeritus
Jul 24, 2002
24,766
134
Harrogate
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() 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

macrumors 68020
Sep 18, 2001
2,166
4
Denver, CO
Indeed, and you can avoid the array copy trivially. Since the homework has already been turned in...

Code:
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

macrumors 6502
Jun 23, 2003
460
0
Recursion hasn't gotten nearly enough love in this thread.

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

robbieduncan

Moderator emeritus
Jul 24, 2002
24,766
134
Harrogate
@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

macrumors 68020
Sep 18, 2001
2,166
4
Denver, CO
@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:

Code:
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

macrumors member
Jun 1, 2005
66
0
London, UK
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

macrumors 68000
Jun 6, 2003
1,952
0
District of Columbia
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.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.