找到给出集合的最长的单词

Question

这是一个谷歌面试问题,我使用HashMap或类似的数据结构在线找到大多数答案.我想尽可能找到使用Trie的解决方案.有人可以给我一些提示吗？

这是一个问题:您将获得一个字典,其形式为每行包含一个单词的文件.例如,

abacus 
deltoid 
gaff 
giraffe 
microphone 
reef 
qar 

您还会收到一系列信件.例如,

{a, e, f, f, g, i, r, q}. 

任务是找到字典中可以拼写字母集合的最长单词.例如,上面示例值的正确答案是"长颈鹿".(注意"礁石"不是一个可能的答案,因为这组字母只包含一个"e".)

Java实现将是首选.

Answer 1

没有Java代码.你可以自己解决这个问题.

假设我们需要做很多次,这就是我要做的:

• 我首先为字典中由26位组成的每个单词创建"签名",如果单词包含一个(或多个)字母实例,则设置位[letter].这些签名可以编码为Java int.

• 然后创建一个映射,将签名映射到具有该签名的单词列表.

要使用预先计算的地图进行搜索:

• 为要查找单词的字母集创建签名.

• 然后迭代映射的键,寻找键在哪里(key & (~signature) == 0).这将为您提供一个"可能"的简短列表,其中不包含任何不在所需字母集中的字母.

• 迭代短名单,查找每个所需字母的正确数字的单词,记录最长的单击.

笔记:

1. 虽然主要搜索大致O(N)是字典中的单词数量,但测试非常便宜.

2. 这种方法的优点是需要相对较小的内存数据结构,(最有可能)具有良好的局部性.这可能有助于加快搜索速度.

这是加快上述O(N)搜索步骤的想法.

上述带有签名的地图开始,创建(预计算),用于所有词语衍生物地图做包含特定双字母; 即一个用于包含AB的单词,用于AC,BC,...和YZ.然后,如果您正在寻找包含(比如说)P和Q的单词,您只需扫描PQ衍生图.这将大大减少O(N)步骤26^2......以额外地图的更多内存为代价.

这可以扩展到3个或更多字母,但缺点是内存使用量激增.

另一个潜在的调整是(以某种方式)将初始字母对的选择偏向于不经常发生的字母/对.但是这会增加一个前期开销,这可能比搜索较短列表所获得的(平均)节省更多.