Preprocess the Dictionary into a hash table where the key is the sorted string of each word and the value being the A list that contains that particular word.(O(nlogn * linked list insertion time some k) )
Now for each given word, sort it(O(nlogn)) and find get the list of words that are anagrams to the given word by looking up the HashTable(O(1)). Thanks, Immanuel On Thu, May 19, 2011 at 11:11 PM, pacific :-) <pacific4...@gmail.com> wrote: > If we were given two strings and asked to check if they have the same > characters (anagrams) : > > @ gene : you are sorting them both ,and trying to match. > cost : sort the first string + sort the second string + compare i.e k * k + > k * k + k .. k is the length of the string. > I presume that bubble sort is nearly optimal for smaller strings if u > consider the overall performance ( its O(n^2) but smaller constants than the > O(nlogn) with larger constants in say quicksort. > > Rather i would suggest , take each character and check that in the other > string. O( k * k) ..in the average case you might do even less than nearly > O(k * k/ 2) if the two strings are not same. > > On Wed, May 18, 2011 at 10:31 AM, anuj agarwal <coolbuddy...@gmail.com>wrote: > >> Same method as Gene told. >> Only enhancement u can made is start from the word nearer to sorted string >> and compare till the nearest word of the reverse of sorted string. >> You don't need to check the whole dictionary. >> >> Anuj Agarwal >> >> Engineering is the art of making what you want from things you can get. >> >> >> >> On Wed, May 18, 2011 at 6:01 AM, Gene <gene.ress...@gmail.com> wrote: >> >>> Sort the characters in the string. Go through the dictionary sorting the >>> characters in each word in turn. Print the words whose sorted versions >>> match the sorted string. >>> >>> You can quickly print all equivalence classes of anagrams in the >>> dictionary by hashing with the sorted strings as keys. It only takes a few >>> seconds to get them all this way with a 2-line perl or ruby script. >>> >>> -- >>> 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 >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> 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 >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > regards, > chinna. > > -- > 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 > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
