Author |
Topic: test char*p is palindrome (Read 980 times) |
|
bbskill
Newbie
Posts: 42
|
 |
test char*p is palindrome
« on: Nov 14th, 2007, 10:29pm » |
 Quote  Modify
|
Hi,
The problem is relative to test whether a given char*p is palindrome.
The normal solution is to get the strlen() of p and then compare itselft from its end and begin.
It is a interview question of ms, and it is asked to improve the speed.
I am wondering whether there exists a faster soluction, maybe using more space complexity for time complexity, for example, hash.
Any suggestion plz.
|
|
 IP Logged |
|
|
|
GowriKumar
Junior Member
 
Gender: 
Posts: 55
|
|
Re: test char*p is palindrome
« Reply #1 on: Nov 15th, 2007, 12:31am » |
Quote Modify
|
on Nov 14th, 2007, 10:29pm, bbskill wrote:Hi,
The problem is relative to test whether a given char*p is palindrome.
The normal solution is to get the strlen() of p and then compare itselft from its end and begin.
It is a interview question of ms, and it is asked to improve the speed. Any suggestion plz. |
|
Was the requirement to improve the speed, based on the above algorithm or after you had implemented the code?
Regards,
Gowri Kumar
|
|
IP Logged |
www.gowrikumar.com
|
|
|
bbskill
Newbie
Posts: 42
|
|
Re: test char*p is palindrome
« Reply #2 on: Nov 15th, 2007, 12:33am » |
Quote Modify
|
Probably not, I believe that is another soluction.
|
|
IP Logged |
|
|
|
Trebla
Newbie
Gender:
Posts: 16
|
|
Re: test char*p is palindrome
« Reply #3 on: Nov 15th, 2007, 1:12pm » |
Quote Modify
|
I'm not sure how time consuming it is to reverse a string in C, but string.reverse().equals(string).
If looping through 1 to n/2 is too slow, I'm really not sure I can think of a faster way...
Again, depending on how efficient reversing a string is, chop the string in half, reverse the half and append it to the original half and compare to the original string (taking extra caution on strings of odd length). But at that point you're doing so many more operations it may just be faster to reverse the whole thing unless it's inordinately long.
|
|
IP Logged |
|
|
|
aditi
Newbie
Posts: 17
|
|
Re: test char*p is palindrome
« Reply #4 on: Nov 15th, 2007, 3:34pm » |
Quote Modify
|
One solution is using hash. It just passes over the string once.
the key in the has table is the char and the value is a list of indices(sorted).
Scan every character and add its index to the corresponding list. You also know the length of string now(say len).
Now process the hash. The condition for the string to be palindrome is:
1. For every character in the hash, the 1st and last index should be equidistant from 1 and len(assuming 1 based index of string)
ie list[first] - 1 = len - list[last]
This should be true for 2nd and 2nd last, 3rd and 3rd last elements and so on in the list.
2. There should only be one character with an odd length list.
Im not sure if this is a faster algorithm than doing two passes because considerable amount of time is spent doing the preprocessing.
For even length strings, using FIFO stack is a nice solution.
|
|
IP Logged |
|
|
|
bbskill
Newbie
Posts: 42
|
|
Re: test char*p is palindrome
« Reply #5 on: Nov 15th, 2007, 8:51pm » |
Quote Modify
|
Could you please give an example?
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: test char*p is palindrome
« Reply #6 on: Nov 16th, 2007, 4:15am » |
Quote Modify
|
@aditi
I think ur solution is slower as comparison to the simple solution i.e. in one scan place two pointers on the list - one at the front and other one at the last, and then just compare the elements as already said above.
Moreover, hash table takes more space than just saving two pointers.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: test char*p is palindrome
« Reply #7 on: Nov 16th, 2007, 5:06am » |
Quote Modify
|
If you compute a single hash key for the string that can be computed forwards and backwards, you can make an approximate "palindromity" test in a single pass. You need a second pass only for actual palindromes or for the rare case where the hash code matches by chance.
I.e.
unsigned int hash1=0;
unsigned int hash2=0;
unsigned int pow=1;
char *p;
for( p=string ; *p ; p++ ){
hash1 = hash1*bigPrime+(*p);
hash2 += pow*(*p);
pow *= bigPrime;
}
if hash1=hash2 you have a good chance that the string is a palindrome. If not, you can reuse p to do a proper test starting from both ends.
|
| « Last Edit: Nov 16th, 2007, 5:08am by Grimbal » |
IP Logged |
|
|
|
bbskill
Newbie
Posts: 42
|
|
Re: test char*p is palindrome
« Reply #8 on: Nov 16th, 2007, 9:17am » |
Quote Modify
|
on Nov 16th, 2007, 5:06am, Grimbal wrote:If you compute a single hash key for the string that can be computed forwards and backwards, you can make an approximate "palindromity" test in a single pass. You need a second pass only for actual palindromes or for the rare case where the hash code matches by chance.
I.e.
unsigned int hash1=0;
unsigned int hash2=0;
unsigned int pow=1;
char *p;
for( p=string ; *p ; p++ ){
hash1 = hash1*bigPrime+(*p);
hash2 += pow*(*p);
pow *= bigPrime;
}
if hash1=hash2 you have a good chance that the string is a palindrome. If not, you can reuse p to do a proper test starting from both ends.
|
|
That is what I thought before. But I don't think it is correct, because it is a approximate soluction. The tip in interview is using space for time, and I don't think this soluction will consume much more space than the soluction using two pointers.
|
|
IP Logged |
|
|
|
Trebla
Newbie
Gender:
Posts: 16
|
|
Re: test char*p is palindrome
« Reply #9 on: Nov 16th, 2007, 10:11am » |
Quote Modify
|
Hmmm... the simple solutions don't seem so simple when you take complex palindromes into question... for instance:
I, man, am regal, a German am I.
and
Do nine men interpret? Nine men, I nod.
Simply reversing the string fails miserably without pre-parsing to remove spaces and punctuation. I'm not savvy enough to tell if the hash works.
The simplest and fastest solution still seems to be starting a pointer at each end, and skipping characters that are non-alphanumeric.
|
|
IP Logged |
|
|
|
GowriKumar
Junior Member
Gender:
Posts: 55
|
|
Re: test char*p is palindrome
« Reply #10 on: Nov 18th, 2007, 10:43pm » |
Quote Modify
|
on Nov 16th, 2007, 5:06am, Grimbal wrote:If you compute a single hash key for the string that can be computed forwards and backwards, you can make an approximate "palindromity" test in a single pass. You need a second pass only for actual palindromes or for the rare case where the hash code matches by chance.
I.e.
unsigned int hash1=0;
unsigned int hash2=0;
unsigned int pow=1;
char *p;
for( p=string ; *p ; p++ ){
hash1 = hash1*bigPrime+(*p);
hash2 += pow*(*p);
pow *= bigPrime;
}
if hash1=hash2 you have a good chance that the string is a palindrome. If not, you can reuse p to do a proper test starting from both ends.
|
|
But will this be faster than the simple equality checking palindrome algorithm?? We anyways are going through the each charaacter in the string and also a second pass.
I accept that it's a different solution, but I suspect this might be slower than the simple one??
Regards,
Gowri Kumar
|
|
IP Logged |
www.gowrikumar.com
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: test char*p is palindrome
« Reply #11 on: Nov 19th, 2007, 12:37am » |
Quote Modify
|
The hash solution is unlikely to be faster than a simple scan.
The idea was to find a way to do it in a single pass, that would make sense if the access to the data is very slow.
Anyway, it doesn't remove the need for a second scan. If the string is not a palindrome, the probability that a second scan is necessary is almost zero. But in all cases where it is a palindrome, a second scan is necessary.
|
|
IP Logged |
|
|
|
shankarke
Newbie
Posts: 1
|
|
Re: test char*p is palindrome
« Reply #12 on: Nov 19th, 2007, 3:53am » |
Quote Modify
|
Keep XOing chars as you go through the string, if you get the o/p as zero, it would mean that its a palindrome.
I think we need to take care of the odd/even length.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: test char*p is palindrome
« Reply #13 on: Nov 19th, 2007, 4:10am » |
Quote Modify
|
on Nov 19th, 2007, 3:53am, shankarke wrote:| Keep XOing chars as you go through the string, if you get the o/p as zero, it would mean that its a palindrome. |
|
No it wouldn't, not even close. It doesn't even mean that some permutation of the string is a palindrome, take "abcd" "bcde" for example.
|
| « Last Edit: Nov 19th, 2007, 5:23am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: test char*p is palindrome
« Reply #14 on: Nov 19th, 2007, 5:15am » |
Quote Modify
|
Almost. "bcde" would xor to zero.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print