Все слова в структуре данных Trie
Я пытаюсь поместить все слова в три строки, слово обозначается eow Поле является истинным для определенного символа в структуре данных Trie, следовательно, у Trie может быть буквы, которые не приводят ни к какому слову, потому что ex «abc» находится в три, но поле «e» eow равно false, поэтому «abc» это не слово
Вот моя структура данных
struct Trie {
bool eow; //when a Trie field isWord = true, hence there is a word
char letter;
Trie *letters[27];
};
и вот моя попытка распечатать все, в основном пытается вернуть все слова в одну строку, разделенных пробелами для слов
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 "";
}
Это не выводит то, что я хочу, какие-либо предложения?
Решение
Вы не используете возвращаемое значение вашего рекурсивного 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;
}
Что бы это ни стоило, это немного неэффективно в том смысле, что оно выделяет много временных строк. Каждый рекурсивный вызов имеет свой words Строка, которая создается, возвращается и уничтожается. Было бы лучше добавить все слова в одну строку.
Также вы можете рассмотреть возможность использования вектора слов вместо добавления их вместе с пробелами. Таким образом, вы можете легче перебирать каждое слово.
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;
Другие решения
Других решений пока нет …