I should clarify my post with that on each next step you partition the partitions.
However, this means that extra space is not zero. Partitioning positions (at least one per bit) need to be stored. So this is no better than just having an array of the counts per character, in terms of space and worse in terms of speed. :-/ [EMAIL PROTECTED] writes: > 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. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
