This will work in fine, but multiplying primes requires arbitrary precision arithmetic for keys of any significant length.
You don't need to compute a hash at all. Just maintain two buffers long enough to hold the longest word and an O(n) sort like counting sort. If you are using Latin (8-bit) characters, you don't even need to complete the counting sort. Just do the counting into arrays of 256 ints. You'll end up with character histograms. It's easy to compare these rather than sorted strings. They require O(2 log C) = O(log C) storage and comparing them needs O(log C) int comparisons, where C is the number of characters in the alphabet. Since C is a constant, this would normally be considered O(1) time and space. On May 26, 2:52 am, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote: > If you sort every word , then you will lose the original word as Ankita > pointed out and if you keep a hashmap to track that it will not be inplace > ., > > Is there any problem in the solution I gave Above , please point it out . > > > > > > > > > > On Fri, May 25, 2012 at 1:14 AM, Anika Jain <anika.jai...@gmail.com> wrote: > > I have a doubt. If u r doing inplace sorting of a word during checks for a > > word, wouldnt that change that word there itself? then how will the > > original anagram get restored to arrange in the output in sorted manner? > > > On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar > > <jitender...@gmail.com>wrote: > > >> The complexity will be (N^2)W because the sorting can be done linear time > >> O(W) for strings. > > >> On Thu, May 24, 2012 at 3:44 PM, WgpShashank <bshashank7andr...@gmail.com > >> > wrote: > > >>> Yeah , its the in-place approach strikes in mind at first look , just > >>> slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of > >>> words in array & W is length of longest word in array , let me know i > >>> missed something ? > > >>> original eat I ate att I the eel eth het > >>> after sorting I I ate att can eat eel eth het the > > >>> output should be I I ate eat att can eel eth het the > > >>> Shashank Mani Narayan > >>> Computer Science & Engineering > >>> Birla Institute of Technology,Mesra > >>> Founder Cracking The Code Lab "http://shashank7s.blogspot.com/"; > >>> FB Pagehttp://www.facebook.com/pages/LestCode > >>> Google+http://gplus.to/wgpshashank > >>> Twitter "https://twitter.com/wgpshashank"; > >>> Puzzled Guy @ "http://ashutosh7s.blogspot.com"; > >>> FB Pagehttp://www.facebook.com/Puzzles.For.Puzzled.Minds > > >>> On May 22, 8:18 am, Navin Gupta <navin.nit...@gmail.com> wrote: > >>> > It can be done inplace, then Time Complexity will be O( N^2 x W ) > >>> where N > >>> > is no. of words and W is word size. > >>> > Start from the left and sort the current word. > >>> > Keep a pointer PTR to the first index of the element left to process. > >>> > Initially it will be 0.As we add words this pointer moves forwards. > >>> > Now iterate the whole list of words to find all those words having same > >>> > sorted sequence i.e. anagrams > >>> > Whenver we get a word which is anagram of the current string, swap it > >>> with > >>> > the string pointed by PTR, move PTR forward. > > >>> > pseudoCode :- > > >>> > func( vector<string> v) > >>> > { > >>> > int n=v.size(); > >>> > for(int i=0;i<n;i++) > >>> > { > >>> > string currentWord = v[i]; > >>> > sort(currentWord); > >>> > for(int j=i+1;j<n;j++) > >>> > { > >>> > if ( sort(v[j]) == currentWord ) // anagrams found, > >>> > { > >>> > swap( v[i] , v[j] ); //move this string > >>> to > >>> > the position next to pos of currentWord > >>> > i++; //and move the > >>> index > >>> > of currentWord forward > >>> > } > >>> > } > > >>> > } > > >>> -- > >>> 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. > > >> -- > >> With regards, > > >> Jitender Kumar > >> 3rd year (Computer Engineering) > >> NIT Kurukshetra > >> Kurukshetra- 136119 > >> Mobile +91-8529035751 > > >> -- > >> 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 > > Anika Jain > > > -- > > 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, > > Jalaj Jaiswal > Software Developer, > Adobe Systems > +91-9019947895 > * > * > FACEBOOK <http://www.facebook.com/jalaj.jaiswal89> > LINKEDIN<http://www.linkedin.com/profile/view?id=34803280&trk=tab_pro> -- 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.
