有没有人看到首页那个笑话阿# Joke - 肚皮舞运动
j*y
1 楼
在看Hacking_a_Google_Interview_Handout_2.pdf，里面提到：
Classic Question #6: Data structure for anagrams
Given an English word in the form of a string, how can you quickly find all
valid anagrams for that string (all valid rearrangements of the letters that form
valid English words)? You are allowed to pre‐compute whatever you want to and
store whatever you optionally pre‐compute on disk.
Answer: We want to use a hash table! If your interviewer really hates hash tables (which they sometimes do for some reason), you can use a tree instead. But let's
assume you can use a hash table. Then for the pre‐computing step, go through each
word 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 table
and the original word as one of the values in a list of values for that key. For
example, the entry for "opst" would be the list ["opts", "post", "stop", "pots", "tops", "spot"]. Then, whenever you get a string, you simply sort the letters of the string and look up the value in the hash table. The running time is O(n log n) for sorting the string (which is relatively small) and approximately O(1) for the lookup in the hash table.
大致可以理解这段话，不过用C或者C++怎么实现啊？高手可否给个具体的code实例？
另外，不用hash table，用C++的map可以吗？
谢了先。
Classic Question #6: Data structure for anagrams
Given an English word in the form of a string, how can you quickly find all
valid anagrams for that string (all valid rearrangements of the letters that form
valid English words)? You are allowed to pre‐compute whatever you want to and
store whatever you optionally pre‐compute on disk.
Answer: We want to use a hash table! If your interviewer really hates hash tables (which they sometimes do for some reason), you can use a tree instead. But let's
assume you can use a hash table. Then for the pre‐computing step, go through each
word 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 table
and the original word as one of the values in a list of values for that key. For
example, the entry for "opst" would be the list ["opts", "post", "stop", "pots", "tops", "spot"]. Then, whenever you get a string, you simply sort the letters of the string and look up the value in the hash table. The running time is O(n log n) for sorting the string (which is relatively small) and approximately O(1) for the lookup in the hash table.
大致可以理解这段话，不过用C或者C++怎么实现啊？高手可否给个具体的code实例？
另外，不用hash table，用C++的map可以吗？
谢了先。
