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 ]
