Edit Distance

Edit Distance is the question behind spell-check and autocorrect. When your phone changes “wrod” to “word”, something is measuring how far apart two words are. This question asks you to find that distance. It looks scary at first. But it becomes calm and clear once you see it as a small grid you fill in one cell at a time.

🎯 The Problem

You get two words. Change the first word into the second word using the fewest edits.

The rules:

• You can insert a letter.
• You can delete a letter.
• You can replace one letter with another.
• Each edit counts as one step. Find the smallest number of steps.

For "horse" and "ros", the answer is 3. You replace h with r. Then you delete o. Then you delete e. Three edits and "horse" becomes "ros".

Input:  word1 = "horse", word2 = "ros"
Output: 3

Explanation:
  horse -> rorse  (replace 'h' with 'r')
  rorse -> rose   (delete 'r')
  rose  -> ros    (delete 'e')

This smallest number of edits has a name. It is called the Levenshtein distance. That is just a plain label for how many single edits turn one string into the other.

Here is a picture of the question. We line up one word along the top and the other word down the side. Every path from the start to the end is one way of editing.

🐢 Approach 1: Plain Recursion (Brute Force)

The idea in one line: look at the last letters, and on a mismatch try insert, delete, and replace.

The idea:

• Think from the end of both words.
• If the last letters are the same, they cost nothing. Keep them and solve the smaller pair.
• If the last letters differ, you must do one edit.

How it works:

• On a mismatch, try inserting, deleting, and replacing.
• Each choice leaves a slightly smaller pair of words.
• Solve each smaller pair the same way. Take the cheapest of the three plus one.

Why it is weak:

• The same small pair of words gets solved again and again from different paths.
• Each step branches into three more.
• The blow-up is roughly O(3^n). Unusable for long words.

Here is the plain recursion code:

def min_distance(word1, word2):
    def dfs(i, j):
        if i == len(word1):
            return len(word2) - j
        if j == len(word2):
            return len(word1) - i
        if word1[i] == word2[j]:
            return dfs(i + 1, j + 1)
        return 1 + min(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1))

    return dfs(0, 0)

🧠 Approach 2: Add Memoization (Better)

The idea in one line: remember the answer for each leftover pair so you solve it once.

The idea:

• The waste comes from solving the same small pair many times.
• The key is “how much of word1 is left” and “how much of word2 is left”.

How it works:

• The first time you solve a pair, store the answer.
• The next time the same pair shows up, read it straight from the table.

Why it is fast:

• Every distinct pair is solved only once.
• There are about m times n pairs, so the time drops to O(m × n). This is memoization.

Here is the memoized recursion:

from functools import lru_cache


def min_distance(word1, word2):
    @lru_cache(None)
    def dfs(i, j):
        if i == len(word1):
            return len(word2) - j
        if j == len(word2):
            return len(word1) - i
        if word1[i] == word2[j]:
            return dfs(i + 1, j + 1)
        return 1 + min(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1))

    return dfs(0, 0)

🚀 Approach 3: Bottom-Up 2D DP Table (Best)

The idea in one line: fill a grid from the empty-string corner, one cell at a time, no recursion.

The idea:

• Make a grid dp with one extra row and one extra column.
• dp[i][j] is the edit distance between the first i letters of word1 and the first j letters of word2.

The base cases:

• Turning a word into an empty string means deleting every letter. So dp[i][0] = i.
• Building a word from nothing means inserting every letter. So dp[0][j] = j.

How each inner cell fills:

• If letter i of word1 matches letter j of word2, no edit is needed. Copy the diagonal dp[i-1][j-1].
• If they differ, take one plus the smallest of three neighbors.
• The cell above dp[i-1][j] is a delete. The left dp[i][j-1] is an insert. The diagonal dp[i-1][j-1] is a replace.

Why it is best:

• Each cell is filled once, so the time is O(m × n).
• It uses simple loops with no recursion stack. This is tabulation.

Here is the filled table for "horse" and "ros". The bottom-right cell holds the final answer, which is 3.

Steps to Solve

1. Let m be the length of word1 and n be the length of word2.
2. Make a grid dp with m + 1 rows and n + 1 columns.
3. Fill the first column so dp[i][0] = i, because that many deletes empties the word.
4. Fill the first row so dp[0][j] = j, because that many inserts builds the word.
5. For each cell, if the two letters match, copy the diagonal dp[i-1][j-1].
6. If they do not match, take 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
7. The answer sits in the bottom-right cell dp[m][n].

#include <stdio.h>
#include <string.h>

int min3(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int editDistance(const char *w1, const char *w2) {
    int m = (int)strlen(w1);
    int n = (int)strlen(w2);
    int dp[64][64];                 // table big enough for small words

    for (int i = 0; i <= m; i++) dp[i][0] = i;   // deletes to empty word1
    for (int j = 0; j <= n; j++) dp[0][j] = j;   // inserts to build word2

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (w1[i - 1] == w2[j - 1]) {        // letters match, no edit
                dp[i][j] = dp[i - 1][j - 1];
            } else {                              // pick cheapest edit + 1
                dp[i][j] = 1 + min3(dp[i - 1][j],      // delete
                                    dp[i][j - 1],      // insert
                                    dp[i - 1][j - 1]); // replace
            }
        }
    }
    return dp[m][n];
}

int main(void) {
    const char *word1 = "horse";
    const char *word2 = "ros";
    printf("%d\n", editDistance(word1, word2));
    return 0;
}

3

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int editDistance(const string& w1, const string& w2) {
    int m = w1.size(), n = w2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 0; i <= m; i++) dp[i][0] = i;   // deletes to empty word1
    for (int j = 0; j <= n; j++) dp[0][j] = j;   // inserts to build word2

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (w1[i - 1] == w2[j - 1]) {        // letters match, no edit
                dp[i][j] = dp[i - 1][j - 1];
            } else {                              // cheapest of three + 1
                dp[i][j] = 1 + min({ dp[i - 1][j],      // delete
                                     dp[i][j - 1],      // insert
                                     dp[i - 1][j - 1] });// replace
            }
        }
    }
    return dp[m][n];
}

int main() {
    string word1 = "horse";
    string word2 = "ros";
    cout << editDistance(word1, word2) << endl;
    return 0;
}

3

public class EditDistance {
    public static int editDistance(String w1, String w2) {
        int m = w1.length(), n = w2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) dp[i][0] = i;   // deletes to empty word1
        for (int j = 0; j <= n; j++) dp[0][j] = j;   // inserts to build word2

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (w1.charAt(i - 1) == w2.charAt(j - 1)) { // match, no edit
                    dp[i][j] = dp[i - 1][j - 1];
                } else {                                     // cheapest + 1
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],   // replace
                                   Math.min(dp[i - 1][j],       // delete
                                            dp[i][j - 1]));     // insert
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        System.out.println(editDistance(word1, word2));
    }
}

3

def edit_distance(w1, w2):
    m, n = len(w1), len(w2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]  # (m+1) x (n+1) grid

    for i in range(m + 1):
        dp[i][0] = i              # delete every letter of word1
    for j in range(n + 1):
        dp[0][j] = j              # insert every letter of word2

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if w1[i - 1] == w2[j - 1]:        # letters match, no edit
                dp[i][j] = dp[i - 1][j - 1]
            else:                              # cheapest of three + 1
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete
                    dp[i][j - 1],      # insert
                    dp[i - 1][j - 1],  # replace
                )
    return dp[m][n]


word1 = "horse"
word2 = "ros"
print(edit_distance(word1, word2))

3

function editDistance(w1, w2) {
  const m = w1.length;
  const n = w2.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; // deletes to empty word1
  for (let j = 0; j <= n; j++) dp[0][j] = j; // inserts to build word2

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (w1[i - 1] === w2[j - 1]) {           // letters match, no edit
        dp[i][j] = dp[i - 1][j - 1];
      } else {                                  // cheapest of three + 1
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],      // delete
          dp[i][j - 1],      // insert
          dp[i - 1][j - 1]   // replace
        );
      }
    }
  }
  return dp[m][n];
}

const word1 = "horse";
const word2 = "ros";
console.log(editDistance(word1, word2));

3

Let us walk through the Python version line by line. Code first, then the why.

m, n = len(w1), len(w2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

We grab both lengths. Then we build a grid with one extra row and one extra column. That extra row and column hold the empty-string cases. Without them the matching rule below would fall off the edge of the table.

for i in range(m + 1):
    dp[i][0] = i
for j in range(n + 1):
    dp[0][j] = j

These two loops fill the borders. Column zero means word2 is empty. To reach an empty word from i letters you delete i times. Row zero means word1 is empty. To build j letters from nothing you insert j times. These known values give the rest of the table something to build on.

if w1[i - 1] == w2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1]

We use i - 1 and j - 1 because the table is shifted by one. Cell dp[i][j] is about the first i and first j letters, so the actual letters sit at index i - 1 and j - 1. When they match, this position adds no cost. We just copy the diagonal, which is the answer for both prefixes without these last two letters.

dp[i][j] = 1 + min(
    dp[i - 1][j],
    dp[i][j - 1],
    dp[i - 1][j - 1],
)

When the letters differ we must spend one edit. The cell above is the delete path. The cell to the left is the insert path. The diagonal is the replace path. We take the smallest of those three already-solved answers and add one for the edit we do now. That single min is the whole heart of the solution.

return dp[m][n]

The bottom-right cell looked at all of word1 against all of word2. So it holds the final smallest edit count, which is 3 here.

⏱️ Time and Space Complexity

Plain recursion branches three ways at every step, so it is exponential and unusable for long words. Memoization solves each distinct pair once, which brings it down to O(m × n). The bottom-up table does the same amount of work with simple loops and no recursion stack. The table itself needs O(m × n) memory. You can shrink that to O(n) by keeping only the previous row, but the full table is easier to explain in an interview.

🧩 Key Takeaways

• ✅ Edit Distance counts the fewest inserts, deletes, and replaces to turn one word into another.
• ✅ The cell dp[i][j] is the distance between the first i and first j letters.
• ✅ When letters match, copy the diagonal. When they differ, take one plus the smallest of three neighbors.
• ✅ The first row and first column are the empty-string base cases.
• ✅ Recursion is exponential, but the 2D table runs in O(m × n) time.

🚀 What’s Next?

• Burst Balloons
• Regular Expression Matching