xisto Community

# 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 on other sites

I am not getting this. .......What is this ?????Is there any test going on? Please give the solution.

##### 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.

`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 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.

`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.

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 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 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 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);      }   }}

##### 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...)

## Create an account

Register a new account

×

• #### Activity

×
• Create New...