wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Palindrome test
        
(Message started by: Aaron on Aug 9^th, 2002, 2:54pm)

Title: Palindrome test
Post by Aaron on Aug 9^th, 2002, 2:54pm

intuitively, I'd do this:

bool isPalindrome(char* str) {
int length = strlen(str);
int testEnd = length / 2;
int tail = length - 1;

for(int index = 0; index < testEnd; index++)
if(str[index] != str[tail - index])
return false
return true;
}

but if I am working on higher level and not caring about optimization,
I'd probably just go like this:

bool isPalindrome(String str) {
return str == reverse(str);
}

However, I can't figure out which of these is the stupid way and which is the smarter way... or are they both stupid? :-/

Title: Re: Palindrome test
Post by -D- on Aug 9^th, 2002, 4:33pm

My intuitively isn't thinking in code :) Seriously though the 2 ways I would do it is: reverse string and then use c-library case insensitive string compare function, or compare first/last letters coming inwards with pointers until the pointers cross or a match doesn't occur. I can't decide which is stupid and smart either, from an algorithm point of view, reversing the string is very straight forward, instantly understandable and doesn't require writing the compare function. But then you do have to write the string reverse function. The other method is a little more obtuse, takes a bit longer to get when you starting at it (not much), but coding wise is almost equivelent in code to reversing a string. I still think it takes a little more work but it's a quicker algorithm too.
-D-

Title: Re: Palindrome test
Post by David Madison on Sep 18^th, 2002, 6:54pm

on 08/09/02 at 14:54:07, Aaron wrote:

for(int index = 0; index < testEnd; index++)
if(str[index] != str[tail - index])

You're walking the entire string, you only need to walk to testEnd/2 rounded up.

on 08/09/02 at 14:54:07, Aaron wrote:

However, I can't figure out which of these is the stupid way and which is the smarter way... or are they both stupid? :-/

Depends on what you're trying to accomplish, right?

Title: Re: Palindrome test
Post by MattyDK23 on May 11^th, 2003, 11:14am

on 09/18/02 at 18:54:06, David Madison wrote:

You're walking the entire string, you only need to walk to testEnd/2 rounded up.

Ummm...no. If you looked closer:

on 08/09/02 at 14:54:07, Aaron wrote:

int length = strlen(str);
int testEnd = length / 2;

testEnd is the string length divided by two. Dividing testEnd by two would give you 1/4 the string length...you'd only traverse the first and last quarters of the string....

However, you bring up a good point about rounding up...testEnd = (int)ceil(length/2)

Title: Re: Palindrome test
Post by S. Owen on May 21^st, 2003, 8:39am

Or instead of rounding up, just use "index <= testEnd"

Title: Re: Palindrome test
Post by Leonid Broukhis on May 21^st, 2003, 8:29pm

There is no need to round up. If the string length is odd, the middle character matches itself - why compare it?

Title: Re: Palindrome test
Post by rene on May 24^th, 2005, 6:41am

the first one is a great code........
takes o(n/2) only...

but i have good code for reversing a string guys ...

void strrev(char *p,int l)
{
if(p<p+l-1)
{
*p^=*(p+l-1)^=*(p)^=*(p+1)
strrev(p+1,l-2);
}
}

Title: Re: Palindrome test
Post by towr on May 24^th, 2005, 8:20am

on 05/24/05 at 06:41:20, rene wrote:

but i have good code for reversing a string guys ...

I'm not sure why you posted that in a thread about palindrome detection, but what the hey..

The gist of it is good. But you seem to have made a slight error in writing it down.

*p^=*(p+l-1)^=*(p)^=*(p+l-1)

And to make it more efficient, you should avoid recursion whenever possible, and instead use iteration. It saves on overhead costs; comparatively a lot for such small functions.
(A good compiler may actualy do this optimization itself, and turn the tail recursion into an iteration)

void strrev(char *p,int l)
{
while(p<p+l-1)
{
*p^=*(p+l-1)^=*(p)^=*(p+l-1);
++p,----l;
}
}

[edited to hide my own stupidity]

Title: Re: Palindrome test
Post by Grimbal on May 24^th, 2005, 9:11am

on 05/24/05 at 08:20:43, towr wrote:

*p^=*(p+l-1)^=*(p)^=*(p+l-1)
strrev(p+1,l-1);

No, you have to use l-2 in the recursion. You remove one char from the beginning, and one from the end.

Besides that, what I also would simplify is to replace (p<p+l-1) by (l>1).

Title: Re: Palindrome test
Post by towr on May 24^th, 2005, 9:51am

on 05/24/05 at 09:11:45, Grimbal wrote:

No, you have to use l-2 in the recursion.

You're right of course.. :-[