• Post Reply Bookmark Topic Watch Topic
  • New Topic

Finding if a Palindrom - Please review  RSS feed

 
Nandini Kalelkar
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, I am a Java newbie and I am working on this piece of code to figure out if a string is a palindrom or not. Could some experts review my code and provide comments on how I could have done it better, if at all? Also, even for this simple program I am using a separate class because I am planning to add more practice problems to my collection in their own classes. Didn't want clutter up one main class. Any help is appreciated. Thanks in advance.

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Despicable Me wrote:Any help is appreciated. Thanks in advance.

Well,

First: Congratulations. A nicely written, descriptive class. I presume it works, otherwise you would have said.

I particularly like your idea of using a Stack (although, these days, a Deque might be better; but that's simply because java.util.Stack is an old class) to check for "reflected" characters. Very good.

Next:
s = ArrayUtils.toObject(in.toCharArray());
is overkill, why not just make s a char[] and use:
s = in.toCharArray();
or indeed, just use in.charOf(n).

Questions:
1. What is a palindrome?
2. Do you think you need to check store every character to work out if s is one?

Winston
 
Nandini Kalelkar
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you very much for your comments. Answers to your Qs:

1. What is a palindrome? A word, phrase that reads the same backward as forward e.g. RACECAR
2. Do you think you need to check store every character to work out if s is one? As per the definition, I thought I had to. But I thought of another implementation here while answering this Q of yours. Please lemme know how it looks to you:


 
Nandini Kalelkar
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
sorry, I didn't realize I had the following still there. I wouldn't need it if I'm going with this second implementation:

 
Paul Clapham
Sheriff
Posts: 22844
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm pretty sure that the goal of this assignment was for you to write some low-level code to solve the problem, so that you would get practice in analyzing problems and solve them. However in a different context, if you just wanted some quick code to identify palindromes and if having a learning experience wasn't important, then this code might be the way to go:


 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nandini Kalelkar wrote:But I thought of another implementation here while answering this Q of yours. Please lemme know how it looks to you:

It looks fine, and what's more you're plainly thinking about the problem, which is the most important thing of all at this stage - oddly enough, probably even more important than whether the solution actually works.

Programming is 80% thought, and you should really only start coding when you can fully describe what you're going to do in English (or your native language).

However, a small thing:
for (int i = 0, j = len - 1; (i <= len / 2) && (j >= len / 2); i++, j--) {
is a bit of a mouthful - particularly the condition in the middle.

How do you think you might make it simpler?

If you feel up to it and you have the time, you might also want to think about a solution that combines aspects of both your tries.
Specifically:
What's the major improvement about your 2nd solution, and how do you think you might use that to improve your Stack-based one?

It's just a suggestion to show you that there's almost always more than one way to solve a problem; and don't worry if you don't have time. What you have is pretty close to optimal.

Winston
 
Rajdeep Biswas
Ranch Hand
Posts: 231
1
Eclipse IDE Java Opera
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nandini Kalelkar wrote:Hi, I am a Java newbie...

Definitely not!!
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:this code might be the way to go:



Does that work for palindrome sentences? I.e. "Madam, I'm Adam" or even "MADAM IM ADAM". Not without some additional coding.

Of course, this may not be a relevant question, depending on the exact specs of the assignment.
 
Nandini Kalelkar
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:for (int i = 0, j = len - 1; (i <= len / 2) && (j >= len / 2); i++, j--) {
is a bit of a mouthful - particularly the condition in the middle.

How do you think you might make it simpler?

Thanks for your time and guidance again. And thanks to everyone else who stopped by and reviewed my code.

Winston Gutkowski - I simply removed the && part and the other condition as I realized it was kind of redundant. It looks like this now: Does it seem better?
fred rosenberger - Yes, I needed some implementation for a better understanding of the language. Thanks for your inputs though.

Winston Gutkowski wrote:
If you feel up to it and you have the time, you might also want to think about a solution that combines aspects of both your tries.
Specifically:
What's the major improvement about your 2nd solution, and how do you think you might use that to improve your Stack-based one?

I am making only one entire pass over the array instead of two in the previous implementation. I also don't need a data structure here.

I am sorry but not sure of ways to simplify it further. Some pointers could help. Thanks again.

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nandini Kalelkar wrote:I simply removed the && part and the other condition as I realized it was kind of redundant. It looks like this now: Does it seem better?

Much; but it can be even simpler:
for (int i = 0, j = len - 1; i < j; i++, j--) {

Do you see why?

I am making only one entire pass over the array instead of two in the previous implementation. I also don't need a data structure here.
I am sorry but not sure of ways to simplify it further. Some pointers could help. Thanks again.

OK, well the reason you're now only doing one pass is that your 2nd solution actually understands the essence of the problem: ie, that the first half of a palindrome mirrors its second half; and for strings with an odd number of characters, you can ignore the centre one.

You're also absolutely right that you don't need the extra structure, but do you see how you could put that knowledge to good use with your Stack-based version? Like I say, don't worry about it if you don't have the time; what you have is pretty near optimal - but stacks are a good structure to get familiar with because they have all sorts of uses.

Oh, and by the way: Well done.

Winston
 
Nandini Kalelkar
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:Much; but it can be even simpler:
for (int i = 0, j = len - 1; i < j; i++, j--) {

Do you see why?

Yes, thanks. i will always be less j. If there are odd number of characters, i will equal j which is also not i<j so the loop will terminate. Here, the program doesn't have to compute len/2 for the condition check.

For using the efficiency of a stack, I guess I can combine these two approaches and store part of the input on stack and pop it and compare to rest half of the array but that doesnt sound quite efficient. Could you please share what you've been meaning to imply by a further optimized approach?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!