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 <[email protected]>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 <[email protected]> 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 [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. > > -- 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 [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.
