c++ - trie 数据结构中的所有单词

Question

我试图将 trie 中的所有单词放入字符串中，单词由 eow 字段表示，对于 trie 数据结构中的某个字符为 true，因此 trie 可以有字母但没有单词，例如“abc”在 trie 中，但“c”的 eow 字段为 false，因此“abc”不是单词

这是我的数据结构

struct Trie {

  bool eow; //when a Trie field isWord = true, hence there is a word
  char letter;
  Trie *letters[27];

}; 

这是我尝试的 print-all 函数，基本上是尝试返回一个字符串中的所有单词，并用空格分隔

string printAll( string word, Trie& data)
{
  if (data.eow == 1)
    return word + " ";
  for (int i = 0; i < 26; i++) {
    if (data.letters[i] != NULL)
     printAll( word + data.letters[i]->letter, *(data.letters[i]));
 }
  return "";
}

它没有输出我想要的内容，有什么建议吗？

Answer 1

您没有使用递归 printAll() 调用的返回值，因此您生成的所有子词都会丢失。尝试这样的事情:

string printAll(string word, const Trie& data)
{
  string words;

  if (data.eow)
    words += word + " ";
  for (int i = 0; i < 26; i++) {
    if (data.letters[i] != NULL)
     words += printAll( word + data.letters[i]->letter, *(data.letters[i]));
  }
  return words;
}

就其值(value)而言，这有点低效，因为它分配了大量临时字符串。每个递归调用都有自己的 words 字符串，该字符串会被构建、返回和销毁。最好将所有单词添加到一个字符串中。

您还可以考虑使用单词 vector ，而不是将它们与空格添加在一起。这样您就可以更轻松地迭代每个单词。

void getWords(const Trie& data, vector<string> &words, string word = "")
{
  if (data.eow)
    words.push_back(word);

  for (int i = 0; i < 26; i++) {
    if (data.letters[i] != NULL)
      getWords(*(data.letters[i]), words, word + data.letters[i]->letter);
  }
}

然后调用它:

vector<string> words;
getWords(trie, words);

for (size_t i = 0; i < words.size(); ++i) {
  if (i > 0)
    cout << " ";

  cout << words[i];
}

cout << endl;