Distanza di modifica
Lezione 9 di 15 del corso Programmazione dinamica 101 di Coddy.
La distanza di modifica, nota anche come distanza di Levenshtein, è una metrica usata per misurare la differenza tra due stringhe. In particolare, è il numero minimo di operazioni necessarie per trasformare una stringa in un’altra.
Le operazioni possibili sono:
- Inserimento: inserire un carattere in una delle stringhe
- Eliminazione: eliminare un carattere da una delle stringhe
- Sostituzione: sostituire un carattere in una delle stringhe con un altro carattere
La distanza di modifica è ampiamente usata in campi come l’elaborazione del linguaggio naturale, la visione artificiale e la bioinformatica.
La programmazione dinamica può essere usata per calcolare in modo efficiente la distanza di modifica tra due stringhe.
Sfida
MedioScrivi una funzione Python edit_distance che accetta due stringhe e restituisce la distanza di modifica tra di esse.
Ad esempio:
edit_distance("kitten", "sitting")dovrebbe restituire 3edit_distance("intention", "execution")dovrebbe restituire 5
Provalo tu
def edit_distance(str1, str2):
# Scrivi il codice quiTutte le lezioni di Programmazione dinamica 101
1Introduzione alla DP
Che cos’è la programmazione dinamica?Perché è importante?Applicazioni in vari campi3Algoritmi di programmazione dinamica
Sottosequenza comune più lungaProblema dello zainoProblema del cambio delle moneteDistanza di modificaEsercitati da solo: Compilatore Python online