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.
