Cerință
Primești două cuvinte a și b. Într-o operație poți insera o literă oriunde în cuvântul curent, poți șterge o literă sau poți înlocui o literă cu alta. Fiecare operație costă 1. Determină costul minim pentru a transforma exact a în b.
Date de intrare
Se citesc cuvintele a și b, pe linii separate.
Date de ieșire
Afișează un singur număr întreg: numărul minim de operații necesare. Dacă a și b sunt identice, răspunsul este 0.
Restricții
1 ≤ lungimea fiecărui cuvânt ≤ 30. Cuvintele conțin numai litere mici a-z. Poți insera și înaintea primei litere sau după ultima literă. Operațiile se aplică succesiv cuvântului obținut până în acel moment.
Explicație
În primul exemplu, ababa devine aba prin ștergerea ultimelor două litere. Lungimile diferă cu 2, deci o singură operație nu poate fi suficientă. În al doilea exemplu, înlocuirea lui a cu b costă o singură operație.
Observații
Selecție Algo25 pentru pregătirea interviurilor: programare dinamică.
Reper tematic pentru pregătire: https://www.hackerrank.com/interview/interview-preparation-kit
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. Literele sunt afișate în ordinea din datele de intrare. Casetele separă pozițiile, inclusiv literele care se repetă.Mărește schema ↗Date de intrare
ababa
aba
Date de ieșire
2
Exemplul 2
Date de intrare
a
b
Date de ieșire
1
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →