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 > <shashank7andr...@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 Page http://www.facebook.com/pages/LestCode >> Google+ http://gplus.to/wgpshashank >> Twitter "https://twitter.com/wgpshashank"; >> Puzzled Guy @ "http://ashutosh7s.blogspot.com"; >> FB Page http://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.
