Prefisso comune più lungo
Lezione 10 di 14 del corso Trie - Serie sulle strutture dati n. 8 di Coddy.
Le prossime sfide sono pensate per usare un Trie.
Usa le classi Trie e TrieNode che hai creato nelle lezioni precedenti (sono disponibili nei file a sinistra). Ogni sfida include un nuovo file solution in cui scriverai una funzione che USA il Trie.
Il nostro primo problema: data una lista di parole, trova il prefisso comune più lungo che condividono tutte. Dopo aver inserito ogni parola in un trie, la risposta è il percorso dalla radice verso il basso, finché a ogni passaggio esiste esattamente un figlio e nessun nodo segna la fine di una parola.
Sfida
FacileScrivi una funzione longestCommonPrefix che riceve un array di stringhe words e restituisce la stringa più lunga che è un prefisso di ogni parola dell’array.
Se l’array è vuoto o non esiste alcun prefisso comune, restituisci una stringa vuota.
Devi usare la classe Trie (fornita in trie insieme a trienode): non usare strutture integrate del 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 = longestCommonPrefix(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