java - 选择一种数据结构来存储句子中的单词及其起始位置

Question

我正在准备面试，经常出现的问题之一是:

呈现一个句子(例如，这首歌是最好的歌曲)，分为单词和单词第一个字母的索引，即“the” - 0, 12； “歌曲”- 4,21； "is"- 9； “最好”- 16；选择一个数据结构来存储该信息，并使用该数据结构重建句子。

我最初的尝试是将单词存储在 HashMap 中，其中键是单词，值是位置数组。这是完全可行的，但由于嵌套的 for 循环和边界索引处的烦人问题、在适当位置的空间中读取等而变得相当复杂。

我已经完成了代码，所以如果有人想看，我会发布(它很长，读起来很引人入胜!!)

无论如何，对于我的问题:任何人都可以提出一种更有效的表示和重建数据的方法吗？我很想尝试另一种方法，但这就是我迄今为止想到的所有方法

Answer 1

作为面试不同技能水平的候选人的人，我希望面试者在决定最终数据结构之前提出更多问题。

• 数据会专门用于重建句子吗？如果是这样，最好有一个列表。
• 您需要能够查找单词位置吗？如果是这样，那么你的结构就很好。
• 对于使用此数据的句子，您可能还会问哪些其他问题？

一种选择是为每个单独的单词创建一个 WordPosition 对象，其中包含该单词、其位置以及对下一个单词的引用。这些将形成一个链表，使得重建句子成为一个简单的有序遍历。将它们存储在 map 中，以单词作为键，并为每个单词提供一个 WordPosition 列表。