Distanța de editare
Scrii „algoritn” și telefonul îți propune „algoritm”. Cum știe ce cuvânt ai vrut? Calculează distanța de editare (distanța Levenshtein): numărul minim de operații de inserare, ștergere sau înlocuire a unui caracter prin care un cuvânt devine celălalt. Este cea mai cunoscută problemă de DP pe două texte, după LCS.
Problema
Primești două texte a și b. O operație modifică un singur caracter din a: îl inserezi, îl ștergi sau îl înlocuiești. Care este numărul minim de operații prin care a devine b?
Scrie funcția distanta_editare(a, b) care returnează numărul minim de inserări, ștergeri și înlocuiri prin care a devine b, cu un tabel DP (n + 1) × (m + 1). Testele sunt deja scrise.
- Creează tabelul și completează cazurile de bază: dp[i][0] = i, dp[0][j] = j.
- Pentru caractere egale copiezi diagonala; altfel 1 + min(...) din cei trei vecini.
- Returnează dp[n][m]. Trebuie să apară: 3, 5, 3, 0.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan