Completamento automatico
Lezione 12 di 14 del corso Trie - Serie sulle strutture dati n. 8 di Coddy.
Questo è il classico caso d'uso per un trie: dato ciò che l'utente ha digitato finora, elenca tutte le parole memorizzate che iniziano con quel prefisso. Raggiungi il nodo del prefisso; se non ci riesci, non restituire nulla. Poi esplora il sottoalbero sottostante e raccogli tutte le parole che trovi.
Mentre scendi durante la DFS, costruisci la parola un carattere alla volta aggiungendo il carattere dell'arco appena attraversato. Ogni volta che raggiungi un nodo in cui isEndOfWord è true, il percorso corrente è una delle corrispondenze.
Sfida
MedioScrivi una funzione autocomplete che riceve un array di stringhe words e una stringa prefix, e restituisce l’elenco delle parole dell’array che iniziano con prefix.
L’elenco restituito deve essere in ordine crescente (alfabetico). Se nessuna parola corrisponde, restituisci un elenco vuoto.
Devi usare la classe Trie (fornita in trie insieme a trienode) - non usare strutture integrate nel linguaggio come insiemi, dizionari o mappe per conteggiare/tenere traccia.
Provalo tu
#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;
}
Tutte le lezioni di Trie - Serie sulle strutture dati n. 8
3Sfide pratiche
Prefisso comune più lungoConta le parole con il prefissoCompletamento automaticoParola più lunga nel dizionarioSuddivisione delle paroleEsercitati da solo: Compilatore C online