[google面试题]Given an English word in the form of a string, how can you quickly find all valid an agrams for that string

(all valid rearrangements of the letters that form validEnglish words) You are allowed to pre-compute what ever you want to and store what ever you optionally pre‐compute on disk.

Answer: We want to use a hashtable!If your interviewer really hates hashtables(which they sometimes do for some reason),you can use a tree instead.But let'sassume you can use a hashtable.Then for the pre‐computing step,go through eachword in the dictionary,sort the letters of the word in alphabetical order(so"hacking" would become "acghikn")and add the sorted letters as a key in the tableand the original word as one of the values in a list of values for that key.Forexample,the entry for "opst" would be the list["opts","post","stop","pots","tops","spot"].Then,when ever you get a string,you simply sort the letters of the string and look up the value in the hashtable.The running time is O(nlogn) for sorting the string(which is relatively small)and approximately O(1) for the look up in the hashtable.There are several other possible answers to this question,but we feel that theanswer above is considered an optimal solution.