Skip to content

Edit Distance

The Levenshtein distance (edit distance) between two strings is the minimum number of insert, delete, and substitute operations to turn one string into the other. It is classic 2D DP over (i, j) = prefixes of length i and j.

Recurrence

Let dp[i][j] = minimum edits to convert a[0..i-1] into b[0..j-1].

  • dp[0][j] = j, dp[i][0] = i
  • If a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]
  • Else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    (delete / insert / substitute)
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int editDistance(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
        }
    return dp[n][m];
}

Space \(O(\min(n,m))\)

Only the previous row of dp is needed to compute the next row.