Algoritmalar
en

Edit Distance

Dynamic Programming O(m · n) O(m · n)

Fewest single-character insertions, deletions or replacements to turn one string into another (Levenshtein).

εεSATURDAY
ε·········
S·········
U·········
N·········
D·········
A·········
Y·········
1/127

Turning "" into the first 0 of "SATURDAY" needs 0 inserts.

Invariantdp[i][j] is the cheapest way to turn the first i of a into the first j of b.

edit-distance.c
int min3(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}
 
int editDistance(const char *a, const char *b) {
    int m = strlen(a), n = strlen(b);
    int dp[m + 1][n + 1];
 
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = j;
            else if (j == 0)
                dp[i][j] = i;
            else if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min3(dp[i - 1][j - 1],
                                    dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

How Edit Distance works

dp[i][j] = cheapest way to turn the first i chars of A into the first j of B. Equal characters cost nothing; otherwise pay 1 for the best of replace (diagonal), delete (up) or insert (left).

When to use it

Spell checking, fuzzy search, diffing, DNA mutation distance.