Back to solutions

Edit Distance

MediumDynamic Programming

Return the minimum number of insertions, deletions, or substitutions to convert word1 into word2.

Open problem
Constraints
  • 0 <= word1.length, word2.length <= 500

2D DP over prefixes

Time O(n * m)Space O(n * m)

dp[i][j] is the edit distance between the first i and j characters. If the current characters match, carry the diagonal; otherwise take one plus the minimum of insert, delete, or replace.

#include <bits/stdc++.h>
using namespace std;

int minDistance(string a, string b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    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++)
            dp[i][j] = a[i-1] == b[j-1] ? dp[i-1][j-1]
                : 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
    return dp[n][m];
}