查找前三个字母相同的段落中的所有单词？

Question

我们如何以最佳方式解决这个问题？有没有解决这个问题的算法？例如：我们输入一些段落并将其作为输出，我们得到如下的字母：

a）1.你2.你的3.我们必须找到并打印所有开始3个字母相同的单词。 4.你自己

二）1.早期2.早期3.最早

这样我们就得到已经开始共同3个字母”

Answer 1

合理的解决方案，这不是太硬段的所有单词编码是为了维护某种类型的地图，其中键是每个单词的前三个字母，并且值是以这三个字母开头的单词集。您可以扫描段落中的单词，对于每个遇到的单词，先剪掉前三个单词，查找与这些字母对应的地图条目，然后将该单词添加到列表中。然后您可以在最后遍历地图，找到包含至少两个单词的所有集合，然后打印出您找到的每个集群。总的来说，这种方法的运行时间是O（L），其中L是段落中所有单词的总长度。要看到这一点，请注意，对于每个单词，我们会对该单词的一个固定大小的前缀执行地图查找，然后将单词的所有字符复制到地图中。总的来说，这最多访问每个角色的次数不变。

Answer 2

Trie带有前三个字符，然后字索引作为叶应该做的伎俩。