GeeCON Prague 2014*
The moose likes Beginning Java and the fly likes palindrome program Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Beginning Java
Bookmark "palindrome program" Watch "palindrome program" New topic
Author

palindrome program

avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
I'm trying to write a program that tells you whether a String is a palindrome, or not an almost palindrome. Almost Palindromes are palindromes once you remove the spaces and punctuations. If you only look at the letters or numbers you will see a Palindrome. Examples of AlmostPalindromes are:

Madam, I'm adam
A MAN, A PLAN, A CANAL, PANAMA

But, on the code I'm working on, it displays the opposite of whatever I want it to.






Could somebody please tell me what I am doing wrong?
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
I tried running your program after fixing the syntax error with ><, and this is the output.

C:\temp>java lab16b
Enter a string ===>> radar
Palindrome: true
Almost Palindrome: true

Do you wish to repeat this program [Y/N]? ===>> y

Enter a string ===>> Madam, I'm Adam
Palindrome: false
Almost Palindrome: true
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
Yes, but if I enter Radar, it gives me this:
Enter a string ===>> Radar
String: Radar
Palindrome: true
Almost Palindrome: true

It is supposed to be:
Enter a string ===>> Racecar

String: Racecar
Palindrome: true
Almost Palindrome: false
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
I don't follow your question. It's doing what it's supposed to do.
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
Wait a minute, I think I see what you're saying. I was confused by your output.

In the isAlmostPal method, you remove any punctuation, if it exists. After that you proceed to find whether the String after removing punctuation is a palindrome or not. (You could make your class more efficient by simply calling the isPal method on the String after you remove the punctuation). However, you don't check for the case of whether there was no puncutation mark.
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
Yeah, that was my problem, but what I don't get is how I check to see if the punctuation marks were removed. Should I use an if else statement?
Adam Price
Ranch Hand

Joined: Nov 11, 2005
Posts: 95
Originally posted by avelin chen:
Yeah, that was my problem, but what I don't get is how I check to see if the punctuation marks were removed. Should I use an if else statement?


Is it true that (by your definition) any true palindrome is not an almostpalindrome? If so, why not just include a check against true palindrome? ie:


Maybe I am not understanding what the criteria are?
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
Never mind, I think that my instructor had a typo. But, he also wants us to do a clearScreen() method, and I can't think of any way to do that.
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
AFAIK, there is not system-independent way to clear the screen in Java. One way is to print out a bunch of blank lines. However, the next line will still print at the bottom instead of at the top. Unfortunately, I don't know any way to get around this as I have never needed to do it before.

Layne


Java API Documentation
The Java Tutorial
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
Okay, I have another question.
I am supposed to add a method that figures out the least palindrome.
Least Palindromes are true palindromes that are created by adding the least number of characters to a string to make it a palindrome. In the examples below, you will see the before and after of each string. Any string can become a palindrome by concatenating the reverse string to itself. The object of the LeastPalindrome is to achieve a Palindrome with a minimum number of characters.

AARDVARK===AARDVARKRAVDRAA
Raceca===RacecaR
MADAM===MADAM
Does anybody have a suggestion on where I should start because I'm out of ideas at this point. Thanks for your time!
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Well, you already have an isPal() method that checks if a String is a palindrome. You can reuse this method by creating various Strings and check if they are palindromes. How can you use the given String to create the Strings you wish to check? What is the shortest String you should check? What is the longest String? Can you find a way to create every possible String that could be formed for your "least palindrome"? Now can you find a way to find the smallest of these?

I would like you to think about it a little. Hopefully these questions will spark some ideas.

Layne
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
Could I possibly divide the String in half, and check from both ends to see if I can insert a letter in there?
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by avelin chen:
Could I possibly divide the String in half, and check from both ends to see if I can insert a letter in there?


That depends. Look at your examples. Are you allowed to add characters to the middle of the String?

Also, I think you might be getting ahead of yourself. What is the first String you should check with your isPal() method? In other words, for a given String s, what is the smallest String that you should check? (Hint: take a look at your examples.)

Layne
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
Consider:
Add the first letter.
Is this a palindrone?

if not
Add the second letter then the first letter
Is this a palindrone?

....


Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Garrett Rowe:
Consider:
Add the first letter.
Is this a palindrone?

Is this really the shortest String you should check?

Layne
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
So, it will like comparing each substring until you get one that is a paindrome right?
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by avelin chen:
So, it will like comparing each substring until you get one that is a paindrome right?


It looks like you are starting down the track I have in mind. First one comment about coding style. The variable name e is not very descriptive. You should use a more descriptive name like lenght. Better yet, just use s1.length() right in your for loop.

For the loop counter, a one-letter ariable name is typically acceptible. Usually we use i and j before we use k, though. Finally, you need to be a little careful about the condition that stops the for loop. Do you really need <= or will < suffice? Of course, this partly depends on what's inside the loop itself and how the counter k is used, so let's go on to figure that out.

So how can you create a new String to test for palindrome-ness? You already seemed to have got my suggestions that the shortest String you need to test is the input String itself. What is the next longest String that you should test? (Hint: Go back to Garett's last post and look at the examples you gave.) Hopefully this will give you an idea of a pattern that will help you fill in the body of the loop.

Good luck!

Layne
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
I think I get the process of doing this, but what I don't get really is after I have found where I nedd to add the letter(s), how do I add it on? I know this sounds dumb, but do I use the concat method? Also, once I have found the palindrome, how do I tell it to stop at that point?
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by avelin chen:
I think I get the process of doing this, but what I don't get really is after I have found where I nedd to add the letter(s), how do I add it on? I know this sounds dumb, but do I use the concat method? Also, once I have found the palindrome, how do I tell it to stop at that point?



Those are some good questions. There are at least two ways you can create the new String. You can concatenate two Strings just by using the + operator. You can also use StringBuilder and it's methods to build the String. I think this is simple enough that using the + operator will suffice.

Since you are writing a method, probably the easiest way to stop is to return the String you found. If you do it right, you can guarantee that the first string you find is the "least" one.

HTH

Layne
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
Would something like this work?
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Well, the best way to find out if it works is by testing it. You should write a main() method that calls your leastPal() method with different Strings. You might want to start by using the examples given and see if the result is what you expect. Can you come up with additional examples that will test your method more thoroughly?

Layne
[ January 22, 2006: Message edited by: Layne Lund ]
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
I figured out how to mmake a least palindrome, but apparently, it is still not quite a least palindrome yet.


For the least palindrome output of Raceca, I get RacecacecaR
It is supposed to be RacecaR

Could somebody please explain to me how to use the least number of letters for the least palindrome?
Am I supposed to use another for loop of some kind?
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Personally, I like your previous solution that uses the substring() method. Unfortunately, it isn't quite right because you don't reverse the characters. See if you can find a way to do this with another method from the API.

I was going to give some hints about how to fix this code, but I think it might help if we back up a little bit. I think you have some understanding of the process that got you to this point. Let's write it out a little bit more clearly. In particular, let's back away from the Java code for a minute and describe the process in something a little closer to English. So far we have decided that we need to create Strings until we find a palindrome. Let's describe this in pseudocode that we can eventually convert into a Java method:

As you can see pseudocode looks a little bit like Java. In this case, I tried to avoid using any Java syntax, but you could easily replace the first line with something like "String leastPal(String s)", which would be less verbose and mean essentially the same thing. However, in pseudocode, you don't have to be so strict about all the little details. For example, I use "loop...end loop" to describe that I need to make some kind of loop. At this point, I don't know if a while or for loop is more appropriate because I'm not entirely sure about all the details. I DO know that I need to keep repeating until I find a "least palindrome". Also, I just said "create a String temp" because I'm not sure about the details of how to create this String.

So the next step is to fill in these details. How do we go about creating the new String that I called temp above? Your previous attempt was on the right track along with the hint I gave earlier.

I hope I'm not wasting your time, but I think we missed out on some important details by jumping right to the Java code to start with. Personally I think it is better to write things out more informally before you start coding an algorithm like this.

Does this help at all?

Layne
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
function leastPal takes String s and returns String loop create a String temp if temp is a palindrom return temp end loopend function

So,


I get what my process should be, but I just don't know how to write it out.
I tried a different way again, but when I typed in Raceca, it went RacecaRaRcaRecaRcecaR



I just want it to stop at the first big R. Arghh this is frustrating
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
I get what my process should be, but I just don't know how to write it out.

That's what I'm trying to explain. You should back away from the Java code and pull out a pencil and paper and try to describe it in words. The words may use concepts that translate to Java constructs (like loops and if statements), but don't worry about the details too much. So can you explain in words how you will take the input String and create a new String (the one I called temp above)?

Layne
avelin chen
Greenhorn

Joined: Dec 11, 2005
Posts: 27
So, I know that if it already a palindrome, it just returns the original String. But, if it is not, then it goes through the least palindrome thing. I know that I want to take the original String and tack it on backwards, but it has to use the least amount of letters. So, I could probably let it go through the isPal thing with the last letter first, and then move forwards, right?
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
One additional thing to think about when solving this problem would be consider the string "acecar". By just adding characters to the end the least palindrone would be "acecaraceca", but you can obviously make a shorter palindrone by adding an 'r' to the beginning of the word. So maybe your program should add both ways and compare the two results to see which one is shorter. Bonus points if they are the same size and you return both in a String[].
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Garrett Rowe:
One additional thing to think about when solving this problem would be consider the string "acecar". By just adding characters to the end the least palindrone would be "acecaraceca", but you can obviously make a shorter palindrone by adding an 'r' to the beginning of the word. So maybe your program should add both ways and compare the two results to see which one is shorter. Bonus points if they are the same size and you return both in a String[].


That's a good point. You might want to consider if you are allowed to append characters to either end to create a "least palindrome." For now, I would concentrate on appending characters to the right-hand side of the String. We can work on appending characters on the left later. Baby steps are definitely the way to go when writing any computer program.

Layne
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by avelin chen:
So, I know that if it already a palindrome, it just returns the original String. But, if it is not, then it goes through the least palindrome thing. I know that I want to take the original String and tack it on backwards, but it has to use the least amount of letters. So, I could probably let it go through the isPal thing with the last letter first, and then move forwards, right?


So can you write this in pseudocode like the example I gave above? Perhaps you can modify my example to fill in these details.

Layne
 
GeeCON Prague 2014
 
subject: palindrome program