j***y
发帖数: 2074 | 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可以吗？
谢了先。 | b*******8
发帖数: 37364 | 2 C++ STL map, Java HashMap，都可以啊。 | j***y
发帖数: 2074 | | j***y
发帖数: 2074 | 4 从网上抄了一段源代码：
－－－
#include
#include | g*****e
发帖数: 282 | 5 我想问hash function怎么设计，曾经被问过。没想出简单好用的function。
find all
letters that form
to and
hash tables (which they sometimes do for some reason), you can use a
tree instead. But let's
through each
order (so
in the table
【在 j***y 的大作中提到】
: 在看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
| t****o
发帖数: 31 | | g*****e
发帖数: 282 | 7 里面也写了那个sample不是hasCode真的implementation。
我想过类似的hash function。至少解这个题是很容易被overflow。any thoughts?
【在 t****o 的大作中提到】
: 可以参考一下 http://en.wikipedia.org/wiki/Java_hashCode()
|
|
