list - 选择数据结构来存储单词并查找它们的出现？

Question

假设我收到了一个包含一堆单词的文档（例如一首诗）。然后我希望能够存储每个单词，以便我可以运行诸如“ocean 4”之类的命令来查找单词“ocean”第四次出现在我的文本中的位置。存储它的最佳数据结构是什么？

我想保持在 O(n^2) 以下，但我认为到目前为止我提出的解决方案效率太低。

任何帮助入门将不胜感激。

谢谢

Answer 1

您可以尝试使用哈希表，其中每个单词都是键，然后使用列表。列表中的每个位置都会存储单词在文本中的位置。例如在 python 中你会调用 myDict["ocean"][4]。