Parola più lunga nel dizionario
Lezione 13 di 14 del corso Trie - Serie sulle strutture dati n. 8 di Coddy.
Dato un dizionario di parole, trova la parola più lunga che può essere costruita un carattere alla volta aggiungendolo a una parola già presente nel dizionario. "world" conta solo se anche "w", "wo", "wor" e "worl" sono parole memorizzate.
È un caso perfetto per un trie. Inserisci ogni parola, poi esegui una DFS dalla radice, ma scendi in un figlio solo se è contrassegnato come isEndOfWord. In questo modo, ogni nodo visitato durante la DFS rappresenta un percorso in cui ogni prefisso è a sua volta una parola.
Tieni traccia del percorso più lungo. Se due percorsi hanno la stessa lunghezza, scegli quello lessicograficamente più piccolo.
Sfida
MedioScrivi una funzione longestWordInDict che riceve un array di stringhe words e restituisce la parola più lunga che può essere costruita aggiungendo un carattere alla volta a una parola più corta dell’array.
Se due parole hanno la stessa lunghezza, restituisci quella lessicograficamente più piccola. Se l’array è vuoto, restituisci una stringa vuota.
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 line[4096];
if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
line[strcspn(line, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(line, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
char* res = longestWordInDict(words, n);
printf("%s\n", 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