palindrome not very proficient...
David J. Gonzo
Greenhorn
Posts: 20
posted 12 years ago
I have a program for a palindrome. The palindrome engine on line 184 works but disregards issues such as capital letters and spaces. So I tried a different engine on line 193 which uses a stack ( i am not familiar with these). Anyway it does not work and I would like to have a palindrome engine that is more proficient. Any ideas where it is going wrong?
You will need the following about() class
Also could you let me know how to integrate the two classes? I am a beginner and am hesitant to mess with things that work....
Thank You in advance!
You will need the following about() class
Also could you let me know how to integrate the two classes? I am a beginner and am hesitant to mess with things that work....
Thank You in advance!
Igor Stojanovic
Ranch Hand
Posts: 58
posted 12 years ago
Hi David,
I will give you friendly advice
You have noticed that nobody answered to your post (more then 1 day) because its too much code posted, can you plz post only relevant part of your code which is making you trouble and then somebody will help you...or try to help you 
kind regards
Igor
I will give you friendly advice
You have noticed that nobody answered to your post (more then 1 day) because its too much code posted, can you plz post only relevant part of your code which is making you trouble and then somebody will help you...or try to help you kind regards
Igor
posted 12 years ago
First, so that others can view the code more simply, lets break out just your two isPalindrome methods, which each use a different algorithm, for easier viewing as Igor suggested - since I'm bored this afternoon, I don't mind doing it for you
Both of these algorithms will produce the same result. Both return true when the word is a case-sensitive palindrome. So "ere" would return true, but "Ere" would not.
Now you ask about efficiency. Let's look at the 193 algorithm. First of all, in my opinion, the stack is not needed. A stack is a LIFO (Last in, First Out) based data structure. It is just like a stack of spring loaded cafeteria plates or a Pez dispenser; the last item into the data structure (via a push), is the first thing out (via a pop). The "purpose" it is serving here is to reverse the order of characters in the String. So this Algorithm does nine things, some of them as many times as there are characters in the string. And it tends to be the more resource intensive things that are done multiple times:
1. Creates a String
2. Creates a Stack Object
3. Iterates through the original String
4. Puts an item (a Character) on a stack String.length times, creating a Character Object each time
5. Iterates though the Stack
6. Pops a Character off the Stack String.length times
7. Converts a Character to a String String.length times
8. Concatenates two Strings together String.length times
9. Checks if two strings are equal
By simply iterating through the String in a reverse order, we can eliminate many of the steps:
Now this algorithm has eliminated multiple (costly and unnecessary) steps to accomplish the same goal. Now we are simply doing steps 1, 3, 8, and 9 from the above list.
This could be made even more efficient by using a StringBuffer instead of a String object. While this adds a "step" or two, StringBuffer appends are significantly more efficient then String concatenations, and is a primary reason the StringBuffer class exists. So this would give us:
So all these different algorithms do the same thing. We have seen how we were able to make your original version 193 more efficient (as 193-B). Now whether the 193-B or 189 is more efficient is a far more involved discussion that we won't get into. One might argue that the 193-B version is easier to read.
Ok, now to another one of your questions/comments. When you say that both of these work, "but disregard issues such as capital letters", do you mean you wish to make them case insensitive, so that "Ere" would return true?
Well, it would be easy to solve this in the 193-B version. If you look at the String class in the Java API you will see that there is a method in it that compares two Strings, but is case insensitive. It's equalsIgnoreCase(). So all you need to do is change the call to the equals() method to equalsIgnoreCase() and your check is no longer case sensitive.
You could change the code in the 189 algorithm so that is is case insensitive. Many intro to Java Programming books either discuss, or have as an exercise, the creation of a method that checks two char primitives to see if they are equal, ignoring case. It is a good exercise to learn about the char primitive and understand characters and character sets. If you searched something like JavaWorld.com, you would also likely find articles on the subject. Lastly, look at the source code for the Java Character class; there are methods in there (such as isUpperCase()) that do similar things that can help you understand case for the primitive char. While you can just use the 193-B algorithm with the equalsIgnoreCase method, I would very strongly recommend, as a learning exercise, you implement the 189 based algorithm so that it ignores case when comparing two char's.
Ok, your next question was about the fact that these algorithms "disregard issues such as capital letters and spaces". After the case insensitivity modification, the sentence "Able was I ere I saw Elba" passes as a palindrome. Are you saying that you want something like "ab ccba" to also pass, such that the extra space is ignored? and it is basically checking "abccba", and "AblewasIereIsawElba" in the case of the above sentence?
While I do not think that is keeping with the true definition of a palindrome, if you want your algorithm to do such, it would be fairly easy. Simply have your method, after receiving the String, but before comparing it, remove all spaces. That should be an easy exercise for you. Just create a new String by iterating through the received String and only putting non-space characters in the new String. Again, I would look at using a StringBuffer to do that. If you get a have any problems, post the your code and someone can help you out with it.
[ February 20, 2005: Message edited by: Mark Vedder ]
[ March 10, 2005: Message edited by: Mark Vedder ]
Both of these algorithms will produce the same result. Both return true when the word is a case-sensitive palindrome. So "ere" would return true, but "Ere" would not.
Now you ask about efficiency. Let's look at the 193 algorithm. First of all, in my opinion, the stack is not needed. A stack is a LIFO (Last in, First Out) based data structure. It is just like a stack of spring loaded cafeteria plates or a Pez dispenser; the last item into the data structure (via a push), is the first thing out (via a pop). The "purpose" it is serving here is to reverse the order of characters in the String. So this Algorithm does nine things, some of them as many times as there are characters in the string. And it tends to be the more resource intensive things that are done multiple times:
1. Creates a String
2. Creates a Stack Object
3. Iterates through the original String
4. Puts an item (a Character) on a stack String.length times, creating a Character Object each time
5. Iterates though the Stack
6. Pops a Character off the Stack String.length times
7. Converts a Character to a String String.length times
8. Concatenates two Strings together String.length times
9. Checks if two strings are equal
By simply iterating through the String in a reverse order, we can eliminate many of the steps:
Now this algorithm has eliminated multiple (costly and unnecessary) steps to accomplish the same goal. Now we are simply doing steps 1, 3, 8, and 9 from the above list.
This could be made even more efficient by using a StringBuffer instead of a String object. While this adds a "step" or two, StringBuffer appends are significantly more efficient then String concatenations, and is a primary reason the StringBuffer class exists. So this would give us:
So all these different algorithms do the same thing. We have seen how we were able to make your original version 193 more efficient (as 193-B). Now whether the 193-B or 189 is more efficient is a far more involved discussion that we won't get into. One might argue that the 193-B version is easier to read.
Ok, now to another one of your questions/comments. When you say that both of these work, "but disregard issues such as capital letters", do you mean you wish to make them case insensitive, so that "Ere" would return true?
Well, it would be easy to solve this in the 193-B version. If you look at the String class in the Java API you will see that there is a method in it that compares two Strings, but is case insensitive. It's equalsIgnoreCase(). So all you need to do is change the call to the equals() method to equalsIgnoreCase() and your check is no longer case sensitive.
You could change the code in the 189 algorithm so that is is case insensitive. Many intro to Java Programming books either discuss, or have as an exercise, the creation of a method that checks two char primitives to see if they are equal, ignoring case. It is a good exercise to learn about the char primitive and understand characters and character sets. If you searched something like JavaWorld.com, you would also likely find articles on the subject. Lastly, look at the source code for the Java Character class; there are methods in there (such as isUpperCase()) that do similar things that can help you understand case for the primitive char. While you can just use the 193-B algorithm with the equalsIgnoreCase method, I would very strongly recommend, as a learning exercise, you implement the 189 based algorithm so that it ignores case when comparing two char's.
Ok, your next question was about the fact that these algorithms "disregard issues such as capital letters and spaces". After the case insensitivity modification, the sentence "Able was I ere I saw Elba" passes as a palindrome. Are you saying that you want something like "ab ccba" to also pass, such that the extra space is ignored? and it is basically checking "abccba", and "AblewasIereIsawElba" in the case of the above sentence?
While I do not think that is keeping with the true definition of a palindrome, if you want your algorithm to do such, it would be fairly easy. Simply have your method, after receiving the String, but before comparing it, remove all spaces. That should be an easy exercise for you. Just create a new String by iterating through the received String and only putting non-space characters in the new String. Again, I would look at using a StringBuffer to do that. If you get a have any problems, post the your code and someone can help you out with it.
[ February 20, 2005: Message edited by: Mark Vedder ]
[ March 10, 2005: Message edited by: Mark Vedder ]
Igor Stojanovic
Ranch Hand
Posts: 58
David Harkness
Ranch Hand
Posts: 1646
posted 12 years ago
Wow, Mark, great post! David certainly benefited from your boredom. I just want to correct a typo since it could confuse a beginner.
I just want to correct a typo since it could confuse a beginner. A stack is a LIFO (Last in, First Out) based data structure. . . . [T]he last item into the data structure (via a push), is the first thing out (via a pop).
David J. Gonzo
Greenhorn
Posts: 20
posted 12 years ago
Special thanks to Mark Vedder for assisting in giving a newbie a shot at one day helping others, cheerio. Igor thanks for the suggestion, and David thanks for the proof.
I am looking foward to many years in programming. After being a fireman for seventeen years I am getting prepared to hang up my firecoat and take on a new career programming...
I am looking foward to many years in programming. After being a fireman for seventeen years I am getting prepared to hang up my firecoat and take on a new career programming...
David Harkness
Ranch Hand
Posts: 1646
posted 12 years ago
Mark, what book did you order? While I've got a bit of a backlog right now sitting on my bookshelf, I'm always curious to see what other ranchers are reading.
David, right on. You've certainly got the perfect attitude to meet the challenge. By the way, sorry about that five alarm on 1st and Figueroa. I never knew amateur rocketry could be so dangerous! 
David, right on. You've certainly got the perfect attitude to meet the challenge.
By the way, sorry about that five alarm on 1st and Figueroa. I never knew amateur rocketry could be so dangerous!
posted 12 years ago
After finishing the awesome Head First Design Patterns, I just ordered Core J2EE Patterns: Best Practices and Design Strategies, Second Edition to continue the solidification of design patterns in my brain. I work primarily in Enterprise Web Applications, and this book seemed like a good next step. Up until know my design pattern knowledge was limited to MVC and some of the other more major ones (Singleton, Factory, and such). So I am trying to rectify that.
I also have about another 30 books on my reading list, which always seems to grow longer, and not shorter despite my best efforts. Hopefully I am not alone in my feeling that there is just so much to learn, and not enough time to learn it. As I often joke, the thing I love the most about the tech field is that there is always something new to learn; and the thing I hate the most about the tech field is there is always something new to learn. It truly is a double-edged sword.
[ February 21, 2005: Message edited by: Mark Vedder ]
Originally posted by David Harkness:
Mark, what book did you order? While I've got a bit of a backlog right now sitting on my bookshelf, I'm always curious to see what other ranchers are reading.
After finishing the awesome Head First Design Patterns, I just ordered Core J2EE Patterns: Best Practices and Design Strategies, Second Edition to continue the solidification of design patterns in my brain. I work primarily in Enterprise Web Applications, and this book seemed like a good next step. Up until know my design pattern knowledge was limited to MVC and some of the other more major ones (Singleton, Factory, and such). So I am trying to rectify that.
I also have about another 30 books on my reading list, which always seems to grow longer, and not shorter despite my best efforts. Hopefully I am not alone in my feeling that there is just so much to learn, and not enough time to learn it. As I often joke, the thing I love the most about the tech field is that there is always something new to learn; and the thing I hate the most about the tech field is there is always something new to learn. It truly is a double-edged sword.
[ February 21, 2005: Message edited by: Mark Vedder ]
David Harkness
Ranch Hand
Posts: 1646
posted 12 years ago
I don't even want to think about all the personal-interest books sitting on my shelf! While it is very exciting, I do hope for a short lull in the pace in the next year or so. For one thing, it helps to have lulls so people can focus energy on standardizing on patterns and best practices for the new technologies. It seems like it's the Wild West again and we're all just running around like mad trying to get work done and learn the new tech.
I feel the same here. I get bored easily, so I love this field because there are always new things around the corner. It seems, however, that in the past two years or so it's ramped up significantly: Hibernate, Spring, AOP, XP. It's tough to keep up.Originally posted by Mark Vedder:
I also have about another 30 books on my reading list, which always seems to grow longer, and not shorter despite my best efforts. Hopefully I am not alone in my feeling that there is just so much to learn, and not enough time to learn it.
I don't even want to think about all the personal-interest books sitting on my shelf! While it is very exciting, I do hope for a short lull in the pace in the next year or so. For one thing, it helps to have lulls so people can focus energy on standardizing on patterns and best practices for the new technologies. It seems like it's the Wild West again and we're all just running around like mad trying to get work done and learn the new tech.
