Author |
Topic: Palindrome test (Read 2064 times) |
|
Aaron
Newbie
Gender: 
Posts: 14
|
 |
Palindrome test
« on: Aug 9th, 2002, 2:54pm » |
 Quote  Modify
|
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? 
|
|
 IP Logged |
|
|
|
-D-
Guest
|
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-
|
|
IP Logged |
|
|
|
David Madison
Guest
|
on Aug 9th, 2002, 2:54pm, 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 Aug 9th, 2002, 2:54pm, 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?
|
|
IP Logged |
|
|
|
MattyDK23
Newbie
Gender:
Posts: 46
|
|
Re: Palindrome test
« Reply #3 on: May 11th, 2003, 11:14am » |
Quote Modify
|
on Sep 18th, 2002, 6:54pm, 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 Aug 9th, 2002, 2:54pm, Aaron wrote:
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
int length = strlen(str);
int testEnd = length / 2;
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)
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: Palindrome test
« Reply #4 on: May 21st, 2003, 8:39am » |
Quote Modify
|
Or instead of rounding up, just use "index <= testEnd"
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Palindrome test
« Reply #5 on: May 21st, 2003, 8:29pm » |
Quote Modify
|
There is no need to round up. If the string length is odd, the middle character matches itself - why compare it?
|
|
IP Logged |
|
|
|
rene
Newbie
Gender: 
Posts: 28
|
|
Re: Palindrome test
« Reply #6 on: May 24th, 2005, 6:41am » |
Quote Modify
|
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);
}
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Palindrome test
« Reply #7 on: May 24th, 2005, 8:20am » |
Quote Modify
|
on May 24th, 2005, 6:41am, 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]
|
| « Last Edit: May 24th, 2005, 9:52am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Palindrome test
« Reply #8 on: May 24th, 2005, 9:11am » |
Quote Modify
|
on May 24th, 2005, 8:20am, 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).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Palindrome test
« Reply #9 on: May 24th, 2005, 9:51am » |
Quote Modify
|
on May 24th, 2005, 9:11am, Grimbal wrote:| No, you have to use l-2 in the recursion. |
|
You're right of course.. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove