在查找数据结构的顺序方面的混乱

Question

今天我参加了一家公司的笔试。整个测试集中在数据结构上。我有个问题我以为我解决了。但我在计算数据结构的Big函数时遇到了困难。我将提供问题和我提出的答案。

给出了您需要存储的文档和文档中的单词，并且应该能够在输入任何单词时返回计数。为您提供了char* GetNextWord()。

1. 您会选择什么数据结构，
2. ，给算法
3. ，您的算法

的顺序是什么？

对于第一个问题，我写到我将选择TRIE数据结构。对于第二个问题，我给出了一个简单的算法。我写道，我将构建TRIE数据结构，如下所示。

struct TRIE{
 boolean isWord;
 int count;
 Node* myList;
}

struct Node{
 char* character;
 Node *next;
 TRIE *child;
}

我有constructTrie()方法，它将对每个单词执行一个addToTrie()。

我写道，addToTrie()的顺序是O(k)，其中k是长度。constructTrie()的顺序是N*O(k)，其中N是字数。

现在我的问题是:我提到的命令是否正确？如果不是，如何在未来解决类似这样的问题(给定ds查找顺序)。我在使用O(k)后感到很困惑。它让我假设O(1)。

提示/提示/建议是开放的！！

编辑：更正了这个问题，明确提到单词计数应该存储在所有唯一的单词中。

Answer 1

如果您真的想使用trie，那么addToTrie()确实是O(k)，其中k是要添加的单词的长度。constructTrie()将使用O(Nk)，其中N是单词的数量，如果您只对每个单词调用addToTrie()。但是，您不需要为每个单词调用addToTrie()函数。添加完单词后，只需将trie指针重置为trie的根，然后在移动当前单词时移动指针，并在进行过程中添加字符。伪码：

trieNode *curr = trieRoot;
for each character c in document
  if it's a word terminator (space etc)
    add a character at curr signaling the end of the current word ('\0' maybe);
    curr = trieRoot;
  else if character is not a separator
    add character c at curr->next->character[c];
    curr = curr->next;

这将给您构建trie的O(C)运行时间，其中C是文档中的字符数。

现在，这就引出了一个问题:为什么你需要trie呢？很明显，你想出了一种方法来检测一个单词何时结束，那么为什么你必须将你的单词添加到一个trie中呢？这太过分了。您需要的唯一数据结构是几个变量:一个用于跟踪当前字符，一个用于跟踪前一个字符，另一个用于计数单词。在O(C)中这样做很容易：

char prev = '\0';
char curr;
int count = 0;

for each character curr
  if curr is a word separator and prev isn't 
    ++count;
  prev = curr;

我认为用trie来解决这个问题是没有意义的，它只会使事情复杂化。我想，如果他们想测试你的尝试知识，他们会给你一个更有意义的问题。

即使他们给了你一个getNextWord()函数(你必须使用它吗？)因为没有它你可以做得更好)，我猜它会返回"\0“或者什么的，当没有更多的单词时？那么，为什么不直接调用它直到它返回"\0“并计数这样的单词呢？不管是哪种情况，在这里都没什么意义。

Answer 2

比较两个泛型字符串需要Θ(k ) (k= most )，而字数是N，您必须仔细观察，所以Ω(Nk)应该是您能得到的最有效的复杂性。