Java Homework (Palindrome)

Discussion in 'Mac Programming' started by zechmann, Oct 28, 2007.

  1. macrumors member

    Joined:
    May 8, 2007
    #1
    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
     
  2. macrumors 6502

    Joined:
    Jul 16, 2004
    Location:
    Milwaukee, WI
    #2
    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.
     
  3. Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
    #3
    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.
     
  4. macrumors 68040

    elppa

    Joined:
    Nov 26, 2003
    #4
    StringBuilder has a reverse method.
     
  5. macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #5
    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. :)
     
  6. thread starter macrumors member

    Joined:
    May 8, 2007
    #6
    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();
     
  7. macrumors 603

    jeremy.king

    Joined:
    Jul 23, 2002
    Location:
    Fuquay Varina, NC
    #7
    reverse() is a StringBuffer method, not String.
     
  8. macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #8
    Convert the input to a StringBuffer. The .reverse() method is a member of StringBuffer, not String.
     
  9. thread starter macrumors member

    Joined:
    May 8, 2007
    #9
    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());
            }
    }
    
     
  10. macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #10
  11. macrumors 601

    zimv20

    Joined:
    Jul 18, 2002
    Location:
    chicago
    #11
    loops are for stanleys. use recursion.
     
  12. thread starter macrumors member

    Joined:
    May 8, 2007
    #12
    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.");
                    }
            }
    }
    
     
  13. macrumors newbie

    Joined:
    Jul 27, 2005
    #13
    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.
     
  14. thread starter macrumors member

    Joined:
    May 8, 2007
    #14
    so how do you make it skip blank spaces and punctuations(, . ? ;)?
     
  15. macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #15
    Scan the buffer for the characters you want to ignore ... and ... IGNORE THEM. :p
     
  16. Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
    #16
    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).
     
  17. macrumors 68020

    Gelfin

    Joined:
    Sep 18, 2001
    Location:
    San Francisco, CA
    #17
    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.
     
  18. thread starter macrumors member

    Joined:
    May 8, 2007
    #18
    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
     
  19. Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
    #19
    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.
     
  20. macrumors 68020

    Gelfin

    Joined:
    Sep 18, 2001
    Location:
    San Francisco, CA
    #20
    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.
     
  21. macrumors 6502

    Joined:
    Jun 23, 2003
    #21
    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]
    }
     
  22. Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
    #22
    @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.
     
  23. macrumors 68020

    Gelfin

    Joined:
    Sep 18, 2001
    Location:
    San Francisco, CA
    #23
    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')) {...}
    
    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.
     
  24. macrumors member

    Joined:
    Jun 1, 2005
    Location:
    London, UK
    #24
    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.
     
  25. macrumors 68000

    savar

    Joined:
    Jun 6, 2003
    Location:
    District of Columbia
    #25
    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.
     

Share This Page