7 replies to this topic

[varalu]

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

What is a palindrome??

Quote

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

[bhavesh]

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

[pointybirds]

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 = true

for (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)))

[varalu]

pointybirds, on Oct 30 2007, 05:56 AM, said:

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 = true

for (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.csse.mona...DS/Tree/Suffix/

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

[apicolet]

pointybirds, on Oct 30 2007, 01:26 AM, said:

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, 23 November 2007 - 12:35 PM.

[songs2enjoy]

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 palindrome
return true;

}

Hope this works faster

[iGuest]

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

 

[iGuest]

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