Edit Distance (rastojanje između stringova)

Edit Distance (uređivačko rastojanje) je klasičan problem dinamičkog programiranja u kome se meri minimalan broj operacija potrebnih da se jedan string pretvori u drugi.

Dozvoljene operacije su:

ubacivanje karaktera
brisanje karaktera
zamena karaktera

Svaka operacija ima cenu 1.

Definicija problema

Data su dva stringa:

s – početni string
t – ciljni string

Potrebno je odrediti minimalan broj operacija da se string s transformiše u string t.

Primer:

s = "kitten"
t = "sitting"

Rezultat: 3 (zamena, zamena, ubacivanje)

Zašto dinamičko programiranje?

Ako posmatramo prefikse stringova, problem se prirodno razlaže na manje podprobleme.

Edit Distance ima:

optimalnu podstrukturu
preklapajuće podprobleme

što ga čini idealnim za dinamičko programiranje.

DP stanje

Definišemo:


dp[i][j] = minimalan broj operacija
da se prvih i karaktera stringa s
pretvori u prvih j karaktera stringa t

Početni uslovi

dp[0][j] = j (ubacivanje j karaktera)
dp[i][0] = i (brisanje i karaktera)

Prelaz (DP relacija)

Ako su poslednji karakteri jednaki:


dp[i][j] = dp[i-1][j-1]

Ako su različiti:


dp[i][j] = 1 + min(
    dp[i-1][j],     // brisanje
    dp[i][j-1],     // ubacivanje
    dp[i-1][j-1]    // zamena
)

Implementacija (C++)


#include <iostream>
#include <string>
using namespace std;

int min3(int a, int b, int c) {
    return min(a, min(b, c));
}

int main() {
    string s, t;
    cin >> s >> t;

    int n = s.size();
    int m = t.size();

    int dp[n + 1][m + 1];

    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            if(i == 0)
                dp[i][j] = j;
            else if(j == 0)
                dp[i][j] = i;
            else if(s[i - 1] == t[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min3(
                    dp[i - 1][j],    // brisanje
                    dp[i][j - 1],    // ubacivanje
                    dp[i - 1][j - 1] // zamena
                );
        }
    }

    cout << "Edit distance: " << dp[n][m];
    return 0;
}

Vremenska i prostorna složenost

Vremenska složenost: O(n · m)
Prostorna složenost: O(n · m)

gde su n i m dužine stringova.

Praktična primena

Edit Distance se koristi u:

proveri pravopisa
preporukama i sličnosti tekstova
bioinformatici (DNK sekvence)
obradi prirodnog jezika

Veza sa drugim DP problemima

Edit Distance je povezan sa:

Longest Common Subsequence (LCS)
Grid DP problemima
problemima poravnanja stringova

Razumevanje ovog problema predstavlja veliki korak ka savladavanju naprednog dinamičkog programiranja.

Interaktivni primer: Coin Change – broj načina (DP tabela)

U ovom primeru možeš vizuelno da vidiš kako se puni DP niz za problem broja načina da se formira data suma.

Primer koristi kovanice {1, 2, 5} i ciljnu sumu 5.

Broj načina da se formira suma (varijacija Coin Change)

Pored najnižeg broja kovanica, čest zadatak je da se odredi koliko različitih načina postoji da se formira data suma koristeći datu listu kovanica, gde svaku kovanicu možemo koristiti neograničeno mnogo puta.

DP ideja

Definišemo:


dp[x] = broj različitih načina da se formira suma x

Početno stanje:

dp[0] = 1 – postoji tačno jedan način da se formira suma 0 (ništa ne uzimamo)

Prelaz:


dp[x] += dp[x - coin]

Za svaku kovanicu i svaki mogući iznos ≥ vrednost te kovanice.

C++ implementacija


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, S;
    cin >> n >> S;

    vector coins(n);
    for(int i = 0; i < n; i++)
        cin >> coins[i];

    vector dp(S + 1, 0);
    dp[0] = 1;

    for(int coin : coins) {
        for(int x = coin; x <= S; x++) {
            dp[x] += dp[x - coin];
        }
    }

    cout << "Broj različitih načina: " << dp[S];
    return 0;
}

Ovaj pristup koristi DP tablicu koja predstavlja sve moguće kombinacije, i važno je da se spoljašnja petlja vrti **po kovanicama**, a unutrašnja **po sumama**, kako bismo izbegli dupliranje brojeva načina.