How does a hash table (or B-tree) determine if the two arrays are the same? A Hash table is hardly O(n) unless you do not hash the strings.
After designing these two structures (for each array) you still have to compare the two to see if they are equal (which if it turns out they are _always_ takes O(n) just for the compare) My suggestion would be to sort the two arrays and compare item per item. You must know that strings are the worst things to sort as they take much longer than numeric values, but you seem to be confined to that. You could try to iterate over each element of the arrays hashing/adding/manipulating each element along the way and compare the two results for equality, this leaves out the sorting part but puts on your shoulders the responsibility of ensuring that duplicate values are as rare as possible and that the operation at each index of the array is not too taxing (i.e. < O(logn)) or you defeate the purpose of avoiding the sort in the first place. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
