选择一个数据结构存储在一个句子中的单词和其起始位置

Question

我准备面试，那往往会拿出一个问题是这样的：

用一句话主办（例如，歌曲是最好的歌曲）分解成单词和单词的第一个字母的索引，即“the” - 0,12; “歌” - 4,21; “是” - 9; “最好” - 16;选择一个数据结构来存储这些信息，并使用该数据结构重构句子。

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

我有代码为它做，所以如果有人想看我会发布（它很长，使铆接阅读!!）

无论如何，对我的问题：任何人都可以提出一个更有效的方式来表示和重建数据？我很想尝试另一种方式，但这是我到目前为止所做的所有

Answer 1

作为一个面试不同技能水平的应聘者，我希望受访者在决定最终数据结构之前提出更多问题。

• 数据将专门用于重建句子吗？如果是这样，一个清单将是可取的。
• 你需要能够查找单词位置？如果是这样，你的结构很好。
• 你可能会问关于使用这些数据的句子的其他问题吗？

一种选择是为每个单词创建一个WordPosition对象，每个单词包含该单词，其位置和对下一个单词的引用。这些将形成一个链表，使重建句子成为一个无关紧要的遍历。将这些文件按照您在地图中的使用方式进行存储，并将每个单词的词作为键和列表WordPosition s。

Answer 2

如何让键位置？然后你不需要使用arrays.and你可以使用树形图，那么集成商将依次返回令牌。

Answer 3

我在这里避免使用地图，因为这看起来太简单了。

class Sentence { 
    String[] words;//Every word in the sentence 
    int[][] word_positions;//{index into the word array,start position of that word in the sentence} 

    String getSentence(){ 
    //Find the last position of the last character of the last word 
    int length = word_positions[word_positions.length][1] 
       + word[word_positions[word_positions.length][0]].length(); 
    //Allocate an appropriate sized array 
    char[] sentence = new char[length]; 

    //Iterate through every word in the sentence, putting it into the correct place. 
    for (int w=0; w<word_positions.length; w++){ 
     //figure out where in the array this word will start 
     int start = word_positions[w][1]; 
     //get the word 
     char[] word = words[wordpositions[w][0].toCharArray(); 
     //copy it into the master array at the correct position 
     for (int letter=0; letter<word.length; letter++) { 
     sentence[start+letter] = word[letter]; 
     } 
    } 

    return sentence.toString(); 
    } 
} 

如果这不包括问题的一部分，请发表评论。我不确定我是否理解所要求的整个范围。