palindrome program

[avelin chen]

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.

   
 
 import java.io.*;
 
public class lab16b
{
 
public static void main (String args[]) throws IOException
{   
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
boolean finished = false;
 
do
{
System.out.print("Enter a string  ===>>  ");
Palindrome p = new Palindrome(input.readLine());        

p.displayData();
System.out.print("\nDo you wish to repeat this program [Y/N]?  ===>>  ");
String repeat=input.readLine();
      boolean right=(repeat.equals("Y") || repeat.equals("yes")||repeat.equals("y")||repeat.equals("YES"));
      if (right)
{

   System.out.println(); 
}
else 
{
System.out.println();
   finished = true;
}
}
while (!finished); 
}
}
 
class Palindrome
{
   private String s1;// stores original string entered at the keyboard
   private String s2;// stores s1 with punctuation and spaces removed
   private boolean palindrome;
   private boolean almostPalindrome;
 
  
   private boolean isPal(String s)
   {
   s1=s1.toLowerCase();
   
   int a=0;
    int b=s1.length()-1;
 
    while (a<b)
    {
      if(s1.charAt(a) != s1.charAt(b))
      {
   
        return false;
      }
      a++;
      b--;
    }
   
    return true; 
  }
 
   
 
   private boolean isAlmostPal()
   {
   s1=s2;
   s2=s2.toLowerCase();
    s2=s2.replaceAll("[^a-zA-Z]+", "");
    
    int a=0;
    int b=s2.length()-1;
 
    while (a><b)
    {
      if(s2.charAt(a) != s2.charAt(b))
      {
   
        return false;
      }
      a++;
      b--;
    }
   
 
   return true; 
  }
   
  
 
 
   public Palindrome(String s)
   {
   s1=s;
   s2="";
   }
 
   public void displayData()
   {
    if (isPal(s1))
   {
      System.out.println("Palindrome: true");
    }
    else
    {
    
      System.out.println("Palindrome: false");
    }
    
    if(isAlmostPal())
     {
      System.out.println("Almost Palindrome: true");
    }
    else
    {
    
      System.out.println("Palindrome: false");
    }
  }
 
}
 
  

Could somebody please tell me what I am doing wrong?

[Keith Lynn]

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]

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]

I don't follow your question. It's doing what it's supposed to do.

[Keith Lynn]

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]

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]

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:

  private boolean isAlmostPal()
   {
if (!isPal(s1)){return false}
else{  [I]your code[/I]  

Maybe I am not understanding what the criteria are?

[avelin chen]

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]

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

[avelin chen]

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]

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]

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]

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]

Consider:
Add the first letter.
Is this a palindrone?

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

....

[Layne Lund]

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]

So, it will like comparing each substring until you get one that is a paindrome right?

   
  private String leastPal()
  {
  if(isPal(s1)==true)
  return s1;
  else
  {
  int e=s1.length();
  for(int k=1; k<=e; k++)
  ???Haven't figured this out yet
 
  }   

[Layne Lund]

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

   
  private String leastPal()
  {
  if(isPal(s1)==true)
  return s1;
  else
  {
  int e=s1.length();
  for(int k=1; k<=e; k++)
  ???Haven't figured this out yet
 
  }   

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]

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]

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]

Would something like this work?

   private String leastPal()
 {
  if(isPal(s1)==true)
  {
    return s1;
  }
  else
  {
  for(int i=s1.length();i>0;i--)
  {
    String s3=s1.substring(0,i);
    String temp=s1+s1.substring(0,i);
  if(isPal(temp))
    {
       return temp;
    }    
 }
 }
}
  

[Layne Lund]

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]

I figured out how to mmake a least palindrome, but apparently, it is still not quite a least palindrome yet.

   private String leastPal()
 {
String temp="";
  if(isPal(s1)==true)
  {
    return s1;
  }
  else
  {
  String leastPal="";
 int n=s1.length()-2;
 for(int i=n; i>=0; i--)
 leastPal+=s1.charAt(i);
   temp=s1+leastPal;
   if(isPal(temp))
    {
       return temp;
       
    }  
 
  return temp;
}
 
}
 

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]

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:

function leastPal takes String s and returns String
    loop
        create a String temp
        if temp is a palindrom
            return temp
    end loop
end function

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]

function leastPal takes String s and returns String loop create a String temp if temp is a palindrom return temp end loopend function

So,

   private String leastPal()
 {
String temp="";<--This would be my function
  if(isPal(s1)==true)
  {
    return s1;
  }
  else
  {
  String leastPal="";
 int n=s1.length()-2;
 for(int i=n; i>=0; i--) <--I'll be creating a temp here
 leastPal+=s1.charAt(i);
   temp=s1+leastPal;
   if(isPal(temp))
    {
       return temp; <--And this will e my return temp
       
    }  
 
  return temp;
}
 
}  

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

  private String leastPal()
 {
String temp="";
int n=0;
  if(isPal(s1)==true)
  {
    return s1;
  }
  else
  {
  String leastPal="";
  for(int k=s1.length(); k>1;k--)
  {
 n=s1.length()-k;
  for(int i=n; i>=0; i--)
  {
  leastPal+=s1.charAt(i);
 temp=s1+leastPal;
   }}
   if(isPal(temp))
    {
       return temp;
       
    }  
 
  return temp;
}
 
}
 
   
  

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

[Layne Lund]

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]

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]

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]

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]

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