• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

Is there better way to check for palindrome string by inserting half of stack  RSS feed

 
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

Below is my code. Is there better way to check for palindrome of string by inserting half of stack and also considering odd and even length ?

 
Saloon Keeper
Posts: 4782
52
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A stack is overkill and so is making a char[]. you should simply use a for() loop with an index and do comparison using charAt(index) vs charAt(length-index-1).
 
Rancher
Posts: 2835
96
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thinking of several ways is both good exercise and often more interesting than a simple for loop. But first of all, clean the string from unwanted characters, like spaces, comma's Et cetera.

Another way (also overkill) is to make a frequency table of the characters. Now, at most one character can have an odd frequency. But that is only a necessary condition, not a sufficient one. So, look at the Collection class, there may be some useful methods available (for instance rotate, but there are some more).
 
Carey Brown
Saloon Keeper
Posts: 4782
52
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This -->

Piet Souris wrote:But first of all, clean the string from unwanted characters, like spaces, comma's Et cetera.


 
raghu kalachar
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey,
Yes I understand stack is overkill but just wanted to try out is their any much more efficient method.
 
Saloon Keeper
Posts: 9255
177
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Like Carey said, the most efficient method is using a simple loop that iterates through the characters of the string from both ends.

Even though it's not the most efficient, I would prefer the clearest solution:

If the solution must be stack-based, I'd use the call stack:

Note that my second example only works for characters that fall within the Basic Multilingual Plane. My first example does work for all other Unicode characters, but does not take combining characters into account. For instance, it may or may not return true for the string "hèh".
 
Ranch Hand
Posts: 231
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why not something as simple as reversing a copy of the string, and then check if they are equal?  Seems much simpler than running through a loop, counting characters, and such.

Just a thought,

Regards,
Robert
 
Sheriff
Posts: 12349
201
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Robert D. Smith wrote:Why not something as simple as reversing a copy of the string, and then check if they are equal?  Seems much simpler than running through a loop, counting characters, and such.


This:

Stephan van Hulst wrote:... I would prefer the clearest solution:


To make it even clearer:

To the point about removing spaces and punctuation, that would be correct if you're checking for imperfect palindromes. The examples given that don't remove spaces and such check for perfect palindromes.
 
Marshal
Posts: 60163
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is really confusing code. If you want to do that sort of thing, simply write return true; In that case you can probably get rid of your boolean local variable.
 
Campbell Ritchie
Marshal
Posts: 60163
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Robert D. Smith wrote:. . . reversing a copy of the string . . .

How would you suggest one should reverse a String?
 
Junilu Lacar
Sheriff
Posts: 12349
201
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

raghu kalachar wrote:
Below is my code.


Compare your code with this cleaned up version:

Alternatively,

This version may seem a little more clever but it is also less clear, in my opinion. It still works the same though.

Try it out here: https://repl.it/@jlacar/StackBasedPalindromeCheck
 
Stephan van Hulst
Saloon Keeper
Posts: 9255
177
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I know I've mentioned this before, but a friendly reminder that that code will only work for characters that fall within the Basic Multilingual Plane. In practice this probably isn't much of a problem, as long as you're not trying to determine whether a string containing unified Han characters or Egyptian hieroglyphs is a palindrome.

For strings containing ligatures or accents, you might have to convert them to either of two normalized Unicode forms, depending on whether you want to consider the reverse of "æ!æ" either "æ!æ" or "ea!ea".

This is not always obvious. For instance, while people usually consider the ligature 'æ' one character, they also usually consider the ligature 'fi' a combination of the 'f' and 'i' characters.
 
Junilu Lacar
Sheriff
Posts: 12349
201
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:I know I've mentioned this before, but a friendly reminder that that code will only work for characters that fall within the Basic Multilingual Plane. In practice this probably isn't much of a problem...


Good reminder but as you said, probably isn't much of a problem. Haven't run into a situation in real life where I actually need to check for palindromes. Really more an academic exercise in algorithms.
 
Campbell Ritchie
Marshal
Posts: 60163
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . Haven't run into a situation in real life where I actually need to check for palindromes. . . .

They occur about every other week in the crossword puzzle. Spoonerisms are slightly less frequent. When I see phrases like, “both ways,”  or, “up and down,” I can suspect the solution will be palindromic. Of course I only use the letters A...Z.
 
Junilu Lacar
Sheriff
Posts: 12349
201
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I meant in a real life programming situation. I don't do crossword puzzles that much either
 
Campbell Ritchie
Marshal
Posts: 60163
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Crossword puzzles are good for you; they prevent dementia by keeping your ??? ??? [What do you call the thing inside your head?] working. Of course I am in England, where crosswords have a twist; the clues are often “cryptic”.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!