SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Advanced

Edit Distance Visualizer

dp[i][j] is the cost to turn the first i letters of A into the first j letters of B. Same letter: copy the diagonal. Otherwise 1 + the cheapest of replace (diagonal), delete (up) or insert (left).

Start the Edit Distance simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(m·n)
Average timeO(m·n)
Worst timeO(m·n)
Extra spaceO(m·n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. First column: turning the first i letters of HORSE into nothing takes i deletes.
  2. First row: building the first j letters of ROS from nothing takes j inserts.
  3. H ≠ R. 1 + min(replace 0, delete 1, insert 1) = 1: replace H with R.
  4. H ≠ O. 1 + min(replace 1, delete 2, insert 1) = 2: replace H with O.
  5. H ≠ S. 1 + min(replace 2, delete 3, insert 2) = 3: replace H with S.
  6. O ≠ R. 1 + min(replace 1, delete 1, insert 2) = 2: replace O with R.
  7. O = O, so no edit is needed: copy the diagonal 1.
  8. O ≠ S. 1 + min(replace 2, delete 3, insert 1) = 2: insert S.
  9. R = R, so no edit is needed: copy the diagonal 2.
  10. R ≠ O. 1 + min(replace 2, delete 1, insert 2) = 2: delete R.
  11. R ≠ S. 1 + min(replace 1, delete 2, insert 2) = 2: replace R with S.
  12. S ≠ R. 1 + min(replace 3, delete 2, insert 4) = 3: delete S.
  13. S ≠ O. 1 + min(replace 2, delete 2, insert 3) = 3: replace S with O.
  14. S = S, so no edit is needed: copy the diagonal 2.
  15. E ≠ R. 1 + min(replace 4, delete 3, insert 5) = 4: delete E.
  16. E ≠ O. 1 + min(replace 3, delete 3, insert 4) = 4: replace E with O.
  17. E ≠ S. 1 + min(replace 3, delete 2, insert 4) = 3: delete E.
  18. HORSE becomes ROS in 3 edits. The green path shows one cheapest way.

Try it with your own input →

2D DP: edit distance in Java, Python, C++, C and JavaScript

int minDistance(String a, String b) {
  int m = a.length(), n = b.length();
  int[][] dp = new int[m + 1][n + 1];
  for (int i = 0; i <= m; i++) dp[i][0] = i;
  for (int j = 0; j <= n; j++) dp[0][j] = j;
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (a.charAt(i - 1) == b.charAt(j - 1))
        dp[i][j] = dp[i - 1][j - 1];
      else
        dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                     Math.min(dp[i - 1][j], dp[i][j - 1]));
    }
  }
  return dp[m][n];
}
def min_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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 - 1],
                                   dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
int minDistance(const string& a, const string& b) {
  int m = a.size(), n = b.size();
  vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
  for (int i = 0; i <= m; i++) dp[i][0] = i;
  for (int j = 0; j <= n; j++) dp[0][j] = j;
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; 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 - 1],
                            dp[i - 1][j], dp[i][j - 1]});
    }
  }
  return dp[m][n];
}
#include <string.h>
#define MIN2(x, y) ((x) < (y) ? (x) : (y))

int minDistance(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++) dp[i][0] = i;
  for (int j = 0; j <= n; j++) dp[0][j] = j;
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (a[i - 1] == b[j - 1])
        dp[i][j] = dp[i - 1][j - 1];
      else
        dp[i][j] = 1 + MIN2(dp[i - 1][j - 1],
                            MIN2(dp[i - 1][j], dp[i][j - 1]));
    }
  }
  return dp[m][n];
}
function minDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1])
        dp[i][j] = dp[i - 1][j - 1];
      else
        dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                                dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
}

In an interview

LeetCode 72, Edit Distance: the fewest inserts, deletes and replaces that turn one word into another.

The first row and column are 0, 1, 2…: turning a word into the empty string takes one delete per letter.

More dynamic programming