从结构中打印单词

Question

对于单元格的以下结构。

struct Trie { 

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

}; 

我试图创建一个自动完成程序的功能，基本上在特里打印出的话给出了具体的字符串前缀

这里是我有：

int wordcheck(TrieNode &node) 
    { 
    if (node.isWord == 1) // you have found your word, so return true 
     { 
     return 1; 
     } 
    for (int i = 0; i < 26; i++) 
     { 
     if (node.letters[i] != NULL && wordcheck(*(node.letters[i]))) 
      { 
      return 1; 
      } 
     } 
    return 0; 
    } 



string find (TrieNode &node, const string &word, string acc) 
{ 
    if (word.length() == 0) 
    { 
     string x = ""; 
     if (node.isWord == 1){ 
     x = " "; 
     int check = 1; 
     for(int i = 0; i < 26; i++) 
     { 
      if (node.letters[i] != NULL && wordcheck(*(node.letters[i]))) 
      { 
       x = x + acc; check = 0; break; 
      } 
     } 
     if(check == 1) 
     { return x; } 
     } 
    for (int i = 0; i < 26; i++){ 
    if (node.letters[i] != NULL && wordcheck(*(node.letters[i]))) 
     { 
     char let = (char)(i + (int)'a'); 
     if (x[x.length() - 1 ] == ' ') 
      { 
      x = x + acc; 
      } 
     x = x + node.letters[i]->letter 
       + find(*(node.letters[i]), word, acc + node.letters[i]->letter); 
     } 
    } 
    return x; 
    } 
else if (node.letters[word[0] - 'a'] == NULL) 
    { return ""; } 
else { 
    return word[0] + find(*(node.letters[ word[0] - 'a']), 
         word.substr(1, word.length()-1), 
         acc + word[0]); 
} 
} 

它似乎工作以外的事实，如果我给它一个长前缀，它将打印短于前缀的单词。我使用累积递归，并确定有一个更有效的方法来做到这一点。我的问题是，如果任何人都可以做到这一点，以便我返回正确的字符串，或者如果可能的话，指导我通过更简单的算法？

Answer 1

我试图创建一个自动完成程序的功能，基本上打印出的话在特里给出了具体的字符串前缀

我不会来分析你的程序 - 对我来说它太复杂了，例如我不知道wordcheck应该做什么？为什么不是bool，而是int？你真的需要检查你的分支机构是否有任何词，你真的有非空的特里没有文字吗？

对于第一 - 打印与给定前缀开头的所有的话 - 你需要去的地方所有这些词开头的节点：

TrieNode* TreeNode::get(std::string word) 
{ 
    TreeNode* retVal = this; 
    for (size_t i = 0; i < word.length(); ++i) { 
    if (Words[i] < 'a' || words[i] > 'z') 
     throw std::runtime_error("Wrong word"); 
    if (retVal->letters[word[i] - 'a'] != NULL) 
     retVal = retVal->letters[word[i] - 'a']; 
    else 
     return nullptr; 
    } 
    return retVal; 
} 

你需要它打印一切从所给的词的功能节点：

void TreeNode::printAll(std::ostream& os, std::string prefix) 
{ 
    if (isWord) 
    os << prefix << "\n"; 
    for (size_t i = 0; i < 26; ++i) { 
    if (retVal->letters[i] != NULL) 
     // this recursive call can be replaced with iterative solution with stack 
     letters[i]->print(os, prefix + char('a' + i)); 
    } 
} 

并结合这些功能 - 给你想要的东西：

void TreeNode::printBeginWith(std::ostream& os, std::string prefix) 
{ 
    TreeNode* node = get(prefix); 
    if (node) 
     node->printAll(os, prefix); 
}