A solution given below taken from cracking the Coding interview book...
Solution is create a Comparator and a small change in compare method is
that u sort the characters of that string and then compare.
and just sort the arrays, using this compareTo method instead of the usual
one.
@jalaj :- we will be sorting a copy of the word and then matching the
sorted_sequence with the sorted_sequence of the copy of other words.
It will still be in-place, because we are using a space of Word size where
the input is a dictionary.
This is an amortized in-place.
--
Navin Kumar Gupta
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)
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.comwrote:
The
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
