Conta le parole con il prefisso
Lezione 11 di 14 del corso Trie - Serie sulle strutture dati n. 8 di Coddy.
Quante parole memorizzate iniziano con un determinato prefisso? Dopo aver inserito ogni parola, percorri il trie dalla radice, un carattere alla volta, seguendo il prefisso. Se manca un carattere, la risposta è zero: nessuna parola può iniziare con quel prefisso.
Se raggiungi la fine del prefisso, arrivi a un nodo. Ogni parola memorizzata che inizia con questo prefisso si trova da qualche parte nel sottoalbero radicato lì. Contale percorrendo il sottoalbero e aggiungendo 1 per ogni nodo in cui isEndOfWord è true.
Sfida
FacileScrivi una funzione countWordsWithPrefix che riceve un array di stringhe words e una stringa prefix, e restituisce il numero di parole nell'array che iniziano con il prefisso dato.
Un prefisso vuoto corrisponde a ogni parola.
Devi usare la classe Trie (fornita in trie insieme a trienode): non usare strutture integrate nel linguaggio come set, dict o map per contare o 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"); }
printf("%d\n", countWordsWithPrefix(words, n, prefix));
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