首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >选择一种数据结构来存储句子中的单词及其起始位置

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

Stack Overflow用户
提问于 2012-04-10 09:06:12
回答 3查看 1.5K关注 0票数 1

我正在准备面试,其中一个问题往往是这样的:

提供句子(例如,歌曲是最好的歌曲),该句子被分解成单词和单词的第一个字母的索引,即," the“- 0,12;" song”- 4,21;" is“- 9;" best”- 16;选择数据结构来存储该信息,并使用该数据结构重构该句子。

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

我已经为它做了代码,所以如果有人想看,我会发布(它很长,是一本引人入胜的读物!!)

无论如何,对于我的问题:有没有人能提出一种更有效的方式来表示和重建数据?我很想尝试另一种方法,但到目前为止我只能想到这一点。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2012-04-10 09:15:33

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

  • 这些数据会被专门用来重建句子吗?如果是的话,列表会更好。
  • 你需要能够查找单词的位置吗?如果是这样的话,你的结构就没问题了。
  • ,关于这个句子,你还会问什么问题?

一种选择是为包含单词、其位置和对下一个单词的引用的每个单词创建一个WordPosition对象。这些将形成一个链表,使得重构句子成为一种简单的顺序遍历。将它们存储在映射中,将单词作为关键字,并为每个单词提供一个WordPosition列表。

票数 1
EN

Stack Overflow用户

发布于 2012-04-10 09:10:05

让键作为位置怎么样?然后你不需要使用arrays.and,你可以使用树映射,然后集成器将按顺序返回令牌。

票数 0
EN

Stack Overflow用户

发布于 2012-04-10 09:25:17

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

代码语言:javascript
复制
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();
  }
}

如果这没有涵盖问题的一部分,请发表评论。我不确定我是否理解了所问问题的全部范围。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/10081800

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档