With the prime number approach you would need to somehow facilitate large numbers. Also, you need to store those primes which would take a lot of space, although admittedly you only need to take that space once. In addition, multiplication is a much heavier opperation than increment.
BiGYaN's approach is nice but does not scale for large strings. If the strings are enourmous then an array of links to the counts with the ability to increase the number of bits in a counter on the fly might work, although that's getting complex and would take space. If space is the main consern, wouldn't some sort of radix sort work here? You could sort the bytes of each string according to one bit (say the least significant of the relevant bits), that would partition the strings into two parts. The sort could be done by starting both from left and right ends and exchanging elements that are not in the appropriate partition (left or right). Once done with the first bit, check if the partitioning position is different, if it is then A is no permitation of B and stop. Otherwise continue with the next relevant bit. This is O(N * w) where w is the number of bits need to be checked before returning FALSE or the total number of relevant bits in a character in the worst case. No additional space required. --Timak "Padmanabhan Natarajan" <[EMAIL PROTECTED]> writes: > How about the prime number approach I mentioned above. Any comments? > > On 4/11/06, Dhyanesh <[EMAIL PROTECTED] > wrote: > > > I also particularly dont like radix sort. Because it is kind of a > hack. It is not a comparison based sort. It will work with characters > as you have here. But what if you have not two strings of characters, > but two arrays of "objects" which you can only "compare". You would > not be able to apply radix sort then. > > -Dhyanesh > > On 4/11/06, Kevin <[EMAIL PROTECTED]> wrote: > > > > Talking about radix sorting, my experience is that many job > > interviewers (who are coders/developer themselvef) do not like it. Each > > time when I mentioned it, they usually did not get happy with it. > > > > What could be the reason? Any bad things in practical for radix > > sorting? > > > > > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
