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 <[email protected]>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 <[email protected]> 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 [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?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 [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?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 [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?hl=en.
