Grade 11 · Dynamic programmingCitește în română

Edit distance

Original: Distanța de editare

O(n²)C++1762 lines2 examples

The idea

What is the minimum number of operations needed to turn the word a into the word b? An operation means inserting, deleting or replacing a letter. d[i][j] is the answer for the first i letters of a and the first j of b. d[i][0] = i (delete everything), d[0][j] = j (insert everything). If a[i] = b[j], d[i][j] = d[i-1][j-1]; otherwise d[i][j] = 1 + min(d[i-1][j] (deletion), d[i][j-1] (insertion), d[i-1][j-1] (replacement)).

Original description (Romanian)

Câte operații sunt necesare, minim, ca să transformăm cuvântul a în cuvântul b? O operație înseamnă inserarea, ștergerea sau înlocuirea unei litere. d[i][j] este răspunsul pentru primele i litere din a și primele j din b. d[i][0] = i (ștergem tot), d[0][j] = j (inserăm tot). Dacă a[i] = b[j], d[i][j] = d[i-1][j-1]; altfel d[i][j] = 1 + min(d[i-1][j] (ștergere), d[i][j-1] (inserare), d[i-1][j-1] (înlocuire)).

Complexity
O(n · m) time and memory
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

soare
stare

Expected output

1
Example 2

Input

carte
cartof

Expected output

2

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

distanta-de-editare.cpp
/*
 * Titlu: Distanța de editare
 * Clasa: 11
 * Capitol: Programare dinamică
 * Descriere: Câte operații sunt necesare, minim, ca să transformăm cuvântul a în cuvântul b?
 *            O operație înseamnă inserarea, ștergerea sau înlocuirea unei litere.
 *            d[i][j] este răspunsul pentru primele i litere din a și primele j din b.
 *            d[i][0] = i (ștergem tot), d[0][j] = j (inserăm tot). Dacă a[i] = b[j],
 *            d[i][j] = d[i-1][j-1]; altfel d[i][j] = 1 + min(d[i-1][j] (ștergere),
 *            d[i][j-1] (inserare), d[i-1][j-1] (înlocuire)).
 * Complexitate: O(n · m) timp și memorie
 *
 * Exemplu
 * Intrare:
 * soare
 * stare
 * Ieșire: 1
 *
 * Exemplu
 * Intrare:
 * carte
 * cartof
 * Ieșire: 2
 */
#include <iostream>
#include <cstring>
using namespace std;

char a[1005], b[1005];
int d[1005][1005];

int main()
{
    cin >> (a + 1) >> (b + 1);
    int n = strlen(a + 1), m = strlen(b + 1);

    for (int i = 0; i <= n; i++)
    {
        d[i][0] = i;
    }
    for (int j = 0; j <= m; j++)
    {
        d[0][j] = j;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i] == b[j])
            {
                d[i][j] = d[i - 1][j - 1];
            }
            else
            {
                d[i][j] = 1 + min(d[i - 1][j - 1], min(d[i - 1][j], d[i][j - 1]));
            }
        }
    }
    cout << d[n][m] << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.