C ++无法让Trie给出正确的搜索词

Question

我正在创建一个单词建议自动完成界面。我正在使用 c++ 中的 trie 来执行此操作。我想在我的代码中输入单词的一部分，并让 trie 建议可能的单词来完成我的单词结尾。

#include<bits/stdc++.h> 
using namespace std; 
#define alphabet (26) 
#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 
struct TrieNode
{ 
struct TrieNode *children[alphabet];
// isWordEnd is true if the node represents
// end of a word
bool isWordEnd;
}; 
struct TrieNode *getNode(void) 
{ 
struct TrieNode *Node = new TrieNode; 
Node->isWordEnd = false; 
for (int i = 0; i < alphabet; i++) 
Node->children[i] = NULL; 
return Node; 
} 
void insert(struct TrieNode *root,  const string key)
{ 
struct TrieNode *Crawl = root;
for (int level = 0; level < key.length(); level++)
{ 
int index = CHAR_TO_INDEX(key[level]); 
if (!Crawl->children[index]) 
{
Crawl->children[index] = getNode(); 
//Crawl = Crawl->children[index];
}
Crawl = Crawl->children[index]; 
}
// mark last node as leaf 
Crawl->isWordEnd = true; 
}
//returns 0 if current node has a child 
// If all children are NULL, return 1. 
bool isLastNode(struct TrieNode* root) 
{ 
for (int i = 0; i < alphabet; i++) 
if (root->children[i]) 
return 0; 
return 1; 
}

void suggestionsRec(struct TrieNode* root, string currPrefix) 
{ 
// found a string in Trie with the given prefix 
if (root->isWordEnd)
{
cout << currPrefix; 
cout << endl;
} 
// All children struct node pointers are NULL 
if (isLastNode(root)) 
{
//currPrefix = "help";
//deleteNode(root);
//delete root;
//root = NULL;
//currPrefix.pop_back();
return;
}

for (int i = 0; i < alphabet; i++) 
{ 
if (root->children[i]) 
{ 
currPrefix.push_back(97 + i); 
//currPrefix.push_back(i);
//currPrefix.pop_back(97 + i);
/*if (isLastNode(root)) 
{
currPrefix.erase(3);
}*/

// recur over the rest 
suggestionsRec(root->children[i], currPrefix); 
//printAutoSuggestions(root->children[i], currPrefix);
} 
} 
} 
// print suggestions for given query prefix. 
int printAutoSuggestions(TrieNode* root, const string query) 
{ 
struct TrieNode* Crawl = root; 
// Check if prefix is present and find the 
// the node (of last level) with last character 
// of given string. 
int level; 
int n = query.length(); 
for (level = 0; level < n; level++) 
{ 
int index = CHAR_TO_INDEX(query[level]); 
// no string in the Trie has this prefix 
if (!Crawl->children[index]) 
return 0; 
Crawl = Crawl->children[index]; 
} 
// If prefix is present as a word. 
bool isWord = (Crawl->isWordEnd == true); 
// If prefix is last node of tree (has no 
// children) 
bool isLast = isLastNode(Crawl); 
// If prefix is present as a word, but 
// there is no subtree below the last 
// matching node. 
if (isWord && isLast) 
{ 
cout << query << endl; 
return -1; 
} 
// If there are are nodes below last 
// matching character. 
if (!isLast) 
{ 
string prefix = query; 
suggestionsRec(Crawl, prefix); 
return 1; 
} 
} 
// Driver Code 
int main() 
{ 
struct TrieNode* root = getNode(); 
insert(root, "hello"); 
insert(root, "dog"); 
insert(root, "hell"); 
insert(root, "cat"); 
insert(root, "a"); 
insert(root, "hel"); 
insert(root, "help"); 
insert(root, "helps"); 
insert(root, "helping"); 
int comp = printAutoSuggestions(root, "hel");
if (comp == -1) 
cout << "No other strings found with this prefixn"; 
else if (comp == 0) 
cout << "No string found with this prefixn"; 
return 0; 
} 

当我输入前缀"hel"时，我想看到

赫尔 地狱 你好 帮助 帮助 帮助

但相反，我只是看到

赫尔 地狱 你好 地狱 地狱平 地狱皮斯

Answer 1

在suggestionsRec(...)中，你有：

for (int i = 0; i < alphabet; i++) 
{
currPrefix.push_back(97 + i);
...
suggestionsRec(root->children[i], currPrefix); 
}
}

您正在向currPrefix添加字符并保留它们。所以你把suggestionsRec叫到后来的孩子身上，currPrefix中的角色不属于那里。