Kevin wrote: > Given two strings A and B, how to quickly check whether they are > permutation or not? > For example, "abcd" and "bcda" are permutation: same chars, just > different order. > > Using hash: hash A and check B will use time O(N), at the cost of extra > N space. How about do not use that much of extra space? > > One naive method: sort A and B by their chars, and do a compare will > take O(NlogN) time. Any faster method?
Use radix sort to make it O(N W) where W is the bit-width of the characters in the string, hence O(N). --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
