Автодополнение
Урок 12 из 14 курса Префиксные деревья (Trie) — Серия «Структуры данных» №8 на Coddy.
Это классический вариант использования префиксного дерева (trie): на основе того, что пользователь уже ввел, вывести список всех сохраненных слов, начинающихся с этого префикса. Перейдите к узлу префикса; если это невозможно, ничего не возвращайте. Затем исследуйте поддерево ниже и соберите все найденные слова.
По мере продвижения вниз во время поиска в глубину (DFS), постепенно формируйте слово, добавляя символ ребра, по которому вы только что прошли. Каждый раз, когда вы попадаете в узел, где isEndOfWord имеет значение true, текущий путь является одним из совпадений.
Задание
СреднеНапишите функцию autocomplete, которая принимает массив строк words и строку prefix, и возвращает список слов из массива, которые начинаются с prefix.
Возвращаемый список должен быть в возрастающем (алфавитном) порядке. Если ни одно слово не подходит, верните пустой список.
Вы должны использовать класс Trie (предоставленный в trie вместе с trienode) — не используйте встроенные средства языка, такие как множества (sets), словари (dicts) или карты (maps) для подсчета или отслеживания.
Попробуйте сами
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char l1[4096], prefix[1024];
if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
l1[strcspn(l1, "\r\n")] = '\0';
prefix[strcspn(prefix, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(l1, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
int out_n = 0;
char** res = autocomplete(words, n, prefix, &out_n);
for (int i = 0; i < out_n; i++) { printf("%s", res[i]); if (i + 1 < out_n) printf(" "); }
printf("\n");
if (res) free(res);
return 0;
}
Все уроки раздела Префиксные деревья (Trie) — Серия «Структуры данных» №8
3Практические задачи
Самый длинный общий префиксПодсчет слов с префиксомАвтодополнениеСамое длинное слово в словареРазбиение строки на слова