Autouzupełnianie
Lekcja 12 z 14 w kursie Drzewa Trie — struktury danych #8 w Coddy.
To klasyczny przypadek użycia drzewa trie: na podstawie tego, co użytkownik wpisał do tej pory, wyświetl wszystkie zapisane słowa zaczynające się od tego prefiksu. Przejdź do węzła odpowiadającego prefiksowi; jeśli nie możesz go znaleźć, nic nie zwracaj. Następnie przeszukaj poddrzewo poniżej i zbierz wszystkie znalezione słowa.
Podczas przechodzenia w dół w trakcie DFS buduj słowo stopniowo, dodając znak krawędzi, którą właśnie przekroczyłeś. Za każdym razem, gdy trafisz na węzeł, w którym isEndOfWord ma wartość true, bieżąca ścieżka jest jednym z dopasowań.
Wyzwanie
ŚredniNapisz funkcję autocomplete, która otrzymuje tablicę ciągów znaków words i ciąg znaków prefix, a następnie zwraca listę słów z tablicy, które zaczynają się od prefix.
Zwrócona lista musi być uporządkowana rosnąco (alfabetycznie). Jeśli żadne słowo nie pasuje, zwróć pustą listę.
Musisz użyć klasy Trie (dostarczonej w trie wraz z trienode) — nie używaj wbudowanych w język struktur, takich jak zbiory, słowniki czy mapy, do zliczania ani śledzenia.
Spróbuj swoich sił
#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;
}
Wszystkie lekcje w sekcji Drzewa Trie — struktury danych #8
3Wyzwania praktyczne
Najdłuższy wspólny prefiksPolicz słowa z danym prefiksemAutouzupełnianieNajdłuższe słowo w słownikuDzielenie słowaPoćwicz samodzielnie: Kompilator C online