Suddivisione delle parole
Lezione 14 di 14 del corso Trie - Serie sulle strutture dati n. 8 di Coddy.
Data una stringa s e un dizionario di parole, possiamo suddividere s in una sequenza di parole del dizionario senza lasciare nulla? "leetcode" può essere suddivisa in "leet" + "code" se entrambe sono nel dizionario; "catsandog" non può essere suddivisa, indipendentemente da come la tagliamo.
Una passata di programmazione dinamica risolve il problema. Definisci dp[i] come i primi i caratteri possono essere segmentati? Inizia con dp[0] = true. Per ogni i per cui dp[i] è true, percorri il trie a partire dalla posizione i nella stringa; ogni volta che il percorso raggiunge un nodo isEndOfWord all'indice j, imposta dp[j+1] = true.
Il trie rende veloce ogni percorso: basta un singolo carattere mancante per interromperlo. La risposta finale si trova in dp[n].
Sfida
MedioScrivi una funzione wordBreak che riceve una stringa s e un array di stringhe dictionary, e restituisce true se s può essere suddivisa in una o più parti senza spazi bianchi, tutte presenti nel dizionario, oppure false altrimenti.
Una s vuota è sempre suddivisibile.
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 s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
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