從結構中打印單詞

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); 
}