wu :: forums - Print Page


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

        riddles >> cs >> test char*p is palindrome
        
(Message started by: bbskill on Nov 14^th, 2007, 10:29pm)

Title: test char*p is palindrome
Post by bbskill on Nov 14^th, 2007, 10:29pm

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.

Title: Re: test char*p is palindrome
Post by gowrikumar on Nov 15^th, 2007, 12:31am

on 11/14/07 at 22:29:43, bbskill wrote:

Was the requirement to improve the speed, based on the above algorithm or after you had implemented the code?

Regards,
Gowri Kumar

Title: Re: test char*p is palindrome
Post by bbskill on Nov 15^th, 2007, 12:33am

Probably not, I believe that is another soluction.

Title: Re: test char*p is palindrome
Post by Trebla on Nov 15^th, 2007, 1:12pm

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.

Title: Re: test char*p is palindrome
Post by aditi on Nov 15^th, 2007, 3:34pm

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.

Title: Re: test char*p is palindrome
Post by bbskill on Nov 15^th, 2007, 8:51pm

Could you please give an example?

Title: Re: test char*p is palindrome
Post by johny_cage on Nov 16^th, 2007, 4:15am

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

Title: Re: test char*p is palindrome
Post by Grimbal on Nov 16^th, 2007, 5:06am

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.

Title: Re: test char*p is palindrome
Post by bbskill on Nov 16^th, 2007, 9:17am

on 11/16/07 at 05:06:35, Grimbal wrote:

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.

Title: Re: test char*p is palindrome
Post by Trebla on Nov 16^th, 2007, 10:11am

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.

Title: Re: test char*p is palindrome
Post by gowrikumar on Nov 18^th, 2007, 10:43pm

on 11/16/07 at 05:06:35, Grimbal wrote:

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

Title: Re: test char*p is palindrome
Post by Grimbal on Nov 19^th, 2007, 12:37am

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.

Title: Re: test char*p is palindrome
Post by shankarke on Nov 19^th, 2007, 3:53am

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.

Title: Re: test char*p is palindrome
Post by towr on Nov 19^th, 2007, 4:10am

on 11/19/07 at 03:53:58, 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.

Title: Re: test char*p is palindrome
Post by Grimbal on Nov 19^th, 2007, 5:15am

Almost. "bcde" would xor to zero.