Печать слов из структуры

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

Кажется, он работает не только потому, что если я задаю ему длинный префикс, он будет печатать слова короче, чем префикс. Я использовал накопительную рекурсию, и я уверен, что есть более эффективный способ сделать это. Мой вопрос: может ли кто-нибудь сделать так, чтобы я вернул правильные строки или, если возможно, провел бы меня по более простому алгоритму?

1

algorithm c++debugging trie

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я пытаюсь создать функцию для программы автозаполнения, которая в основном выводит слова в три с заданным префиксом строки

Я не собираюсь анализировать вашу программу — для меня это слишком сложно, например, Я не понимаю, что wordcheck должен делать? Почему нет bool но int? Вы действительно должны проверить, что в вашей подтрие есть какое-либо слово, действительно ли у вас есть непустое Trie без слов?

Во-первых, чтобы напечатать все слова, которые начинаются с данного префикса, вам нужно перейти в узел, где начинаются все эти слова:

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

0