Jump to content
xisto Community
varalu

Data Structures -- String -- Palindrome Check if a string is a palindrome...

Recommended Posts

Write an algorithm to check whether a given string is palindrome or not in time complexity O(n)

 

What is a palindrome??

A palindrome is a word, phrase, number or other sequence of units that has the property of reading the same in either direction (the adjustment of punctuation and spaces between words is generally permitted). Composing literature in palindromes is an example of constrained writing. The word "palindrome" was coined from Greek roots palin (πάλιν; "back") and dromos (δρ?μος; "way, direction") by English writer Ben Jonson in the 1600s. The actual Greek phrase to describe the phenomenon is karkinik? epigraf? (καρκινική επιγραφή; crab inscription), or simply karkini?oi (καρκινιήοι; crabs), alluding to the backward movement of crabs, like an inscription which can be read backwards.

Make a note that the solution has to be in O(n).

Share this post


Link to post
Share on other sites

Yes, there's a test and if you fail you'll be sent to Siberia. Unless you're from Siberia, then you'll just be hit with a cricket bat.

How about:

for (0 to halfway through string) {  push letter onto stack}is_palindrome = truefor (halfway through string to end of string) {  if letter != (pop letter from stack)	 is_palindrome = false	 end for loop  }}

Or, if you want to save your typing fingers and know some perl, use this comparison:

(substr($str,0,length($str)/2) eq reverse(substr($str,-length($str)/2)))

Share this post


Link to post
Share on other sites

Yes, there's a test and if you fail you'll be sent to Siberia. Unless you're from Siberia, then you'll just be hit with a cricket bat.

 

How about:

 

for (0 to halfway through string) {  push letter onto stack}is_palindrome = truefor (halfway through string to end of string) {  if letter != (pop letter from stack)	 is_palindrome = false	 end for loop  }}

Or, if you want to save your typing fingers and know some perl, use this comparison:

 

(substr($str,0,length($str)/2) eq reverse(substr($str,-length($str)/2)))

 

Thats an very good algorithm.

And your perl thing is good.

 

More solutions:

 

The Solution to this problem is using a tree called Suffix tree. Using the suffix tree most of the string related problems can be solved.

 

The following problems can be solved using suffix tree in O(n) .

1. Longest Repeated Substring

2. Longest Common Substring

3. Palindromes.

 

go through this link

 

http://www.allisons.org/ll/AlgDS/Tree/Suffix/

 

Im not able to understand the Suffix tree construction part. If someone can explain me it ll be useful.

Share this post


Link to post
Share on other sites

Or, if you want to save your typing fingers and know some perl, use this comparison:

(substr($str,0,length($str)/2) eq reverse(substr($str,-length($str)/2)))

Well, that would work indeed, but what about :
$str eq reverse($str)
That is actually the very definition of the plaindrome, and it further saves your fingers, beyond being easier to understand (which I know isn't what we look for in Perl :) )
Edited by apicolet (see edit history)

Share this post


Link to post
Share on other sites

In java

It can be like this

// lets take testString="SAS"boolean isPalindrome(String testString){int length=testString.length();for(int i=0;i<length/2;i++) if(testString[i]!=testString[length-i+1])  return false;//else it's palindromereturn true;}

Hope this works faster

Share this post


Link to post
Share on other sites

Your method will not work because your String is not an Array but this is as small as I could get it in Java. I apologize if it does not come out in the code box thingy but only if you care.

Public class palindrome{Boolean isPalindrome(String testString){   return(testString.Equals(reverse(testString)));}public static String reverse(String s){   String and;     if (s.Length() <= 1)   return s;     else{      char lastC = s.CharAt(s.Length()-1);     String stringLeft = s.Substring(0, s.Length() -1);   return and = lastC + reverse(stringLeft);      }   }}

-reply by That Guy

 

Share this post


Link to post
Share on other sites

Time complexity definitely not O(and) for that piece of code. (And you can address Strings with same syntax as arrays...)

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

Terms of Use | Privacy Policy | Guidelines | We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.